streamalism.org

1. Uvod

U ovom uputstvu naučit ćemo o Radix Sort, analizirati njegovu izvedbu i pogledati njegovu primjenu.

Ovdje se usredotočujemo na korištenje Radix Sort za sortiranje cijelih brojeva, ali nije ograničeno samo na brojeve. Pomoću nje možemo sortirati druge vrste kao što su Niz, isto.

Kako bi bilo jednostavnije, usredotočit ćemo se na decimalni sustav u kojem su brojevi izraženi u bazi (radix) 10.

2. Pregled algoritma

Radix sortiranje je algoritam za sortiranje koji sortira brojeve na temelju položaja njihovih znamenki. U osnovi, koristi vrijednost mjesta znamenki u broju. Za razliku od većine ostalih algoritama za sortiranje, poput Merge Sort, Insertion Sort, Bubble Sort, on ne uspoređuje brojeve.

Radix sortiranje koristi stabilni algoritam sortiranja kao potprogram za sortiranje znamenki. Ovdje smo koristili varijantu brojanja sortiranja kao potprogram koji radix koristi za sortiranje znamenki u svakom položaju. Brojanje sortiranja stabilan je algoritam sortiranja i dobro funkcionira u praksi.

Radix sortiranje djeluje sortiranjem znamenki od najmanje značajne znamenke (LSD) do najznačajnije znamenke (MSD). Također možemo implementirati Radix sortiranje za obradu znamenki iz MSD-a.

3. Brzi primjer

Pogledajmo kako to funkcionira na primjeru. Razmotrimo sljedeći niz:

Ponavljanje 1:

Sortirat ćemo ovaj niz obrađivanjem znamenki iz LSD-a i pomicanjem prema MSD-u.

Počnimo sa znamenkama na jednom mjestu:

Nakon prve iteracije, niz sada izgleda ovako:

Imajte na umu da su brojevi poredani prema znamenkama na jednom mjestu.

Ponavljanje 2:

Prijeđimo na znamenke na desetke:

Sada niz izgleda ovako:

Vidimo da je broj 7 zauzeo prvo mjesto u nizu jer na mjestu desetaka nema nijednu znamenku. O ovome bismo također mogli razmišljati kao da imamo 0 na desetici.

Ponavljanje 3:

Prijeđimo na znamenke u položaju stotine:

Nakon ove iteracije niz izgleda ovako:

I algoritam se ovdje zaustavlja, sa svim elementima poredanim.

4. Provedba

Pogledajmo sada provedbu.

void sort (int [] brojevi) {int maximumNumber = findMaximumNumberIn (brojevi); int numberOfDigits = izračunajBrojDigita u (maksimalanBroj); int placeValue = 1; while (numberOfDigits--> 0) {applyCountingSortOn (numbers, placeValue); placeValue * = 10; }}

Algoritam funkcionira tako što se sazna maksimalan broj u nizu, a zatim izračuna njegova duljina. Ovaj nam korak pomaže da izvršimo potprogram za svaku vrijednost mjesta.

Na primjer, u nizu, [7, 37, 68, 123, 134, 221, 387, 468, 769], maksimalan broj je 769, a njegova duljina 3.

Dakle, tri puta ponovimo i primijenimo potprogram na znamenke u svakom položaju:

void applyCountingSortOn (int [] brojevi, int placeValue) {int raspon = 10 // decimalni sustav, brojevi od 0-9 // ... // izračunavanje učestalosti znamenki za (int i = 0; i <duljina; i ++ ) {int znamenka = (brojevi [i] / mjestoVrijednost)% raspona; frekvencija [znamenka] ++; } za (int i = 1; i = 0; i--) {int znamenka = (brojevi [i] / mjestoVrijednost)% raspona; sortedValues ​​[učestalost [znamenka] - 1] = brojevi [i]; frekvencija [znamenka] -; } System.arraycopy (rezultat, 0, brojevi, 0, duljina); }

U potprogramu smo koristili radix (raspon) za brojanje pojave svake znamenke i povećanje njene učestalosti. Dakle, svaka kanta u rasponu od 0 do 9 imat će neku vrijednost na temelju učestalosti znamenki. Zatim koristimo frekvenciju za pozicioniranje svakog elementa u nizu. To nam također pomaže da minimiziramo prostor potreban za sortiranje niza.

Ajmo sada testirati našu metodu:

@Test javna praznina givenUnsortedArray_whenRadixSort_thenArraySorted () {int [] brojevi = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort (brojevi); int [] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals (numbersSorted, numbers); }

5. Radix Sort vs Brojanje Sort

U potprogramu, duljina frekvencija niz je 10 (0-9). U slučaju Brojanja sortiranja ne koristimo domet. Duljina frekvencija polje bit će maksimalan broj u nizu + 1. Dakle, ne dijelimo ih u kante dok Radix Sort koristi kante za sortiranje.

Brojanje sortiranja prilično je učinkovito kada duljina niza nije puno manja od maksimalne vrijednosti u nizu, dok Radix Sort omogućuje veće vrijednosti u nizu.

6. Složenost

Izvedba Radix Sort ovisi o stabilnom algoritmu za sortiranje koji je odabran za sortiranje znamenki.

Ovdje smo za sortiranje niza koristili Radix Sort n brojevi u bazi b. U našem slučaju osnova je 10. Primijenili smo sortiranje brojanja d puta gdje d označava broj znamenki. Tako vremenska složenost Radix Sort postaje O (d * (n + b)).

Složenost prostora je O (n + b) budući da smo ovdje koristili varijantu Brojanja sorte kao potprogram.

7. Zaključak

U ovom smo članku opisali algoritam sortiranja Radix i ilustrirali kako ga implementirati.

Kao i obično, implementacije koda dostupne su na Githubu.