streamalism.org

1. Introduksjon

I denne opplæringen lærer vi om Radix Sort, analyserer ytelsen og ser på implementeringen.

Her fokuserer vi på å bruke Radix Sort for å sortere heltall, men det er ikke begrenset til bare tall. Vi kan bruke den til å sortere andre typer som Streng, også.

For å holde det enkelt, vil vi fokusere på desimalsystemet der tallene uttrykkes i base (radix) 10.

2. Algoritmeoversikt

Radix sort er en sorteringsalgoritme som sorterer tall basert på posisjonene til sifrene deres. I utgangspunktet bruker den stedverdien til sifrene i et tall. I motsetning til de fleste andre sorteringsalgoritmer, for eksempel Merge Sort, Insertion Sort, Bubble Sort, sammenligner det ikke tallene.

Radix-sortering bruker en stabil sorteringsalgoritme som en underrutine for å sortere sifrene. Vi har brukt en variant av tellesortering som en underrutine her som bruker radiksen til å sortere sifrene i alle posisjoner. Counting sort er en stabil sorteringsalgoritme, og den fungerer bra i praksis.

Radix-sortering fungerer ved å sortere sifre fra LSD (Minst Significant Digit) til MSD (Most Significant Digit). Vi kan også implementere Radix-sortering for å behandle sifre fra MSD.

3. Et raskt eksempel

La oss se hvordan det fungerer med et eksempel. La oss vurdere følgende matrise:

Iterasjon 1:

Vi sorterer denne matrisen ved å behandle sifre fra LSD og gå mot MSD.

Så la oss starte med sifrene på stedet:

Etter den første iterasjonen ser matrisen nå ut som:

Merk at tallene er sortert etter sifrene på stedet.

Iterasjon 2:

La oss gå videre til sifrene ti ganger:

Nå ser matrisen ut:

Vi ser at tallet 7 har okkupert den første posisjonen i matrisen siden den ikke har noe siffer på ti-plassene. Vi kan også tenke på dette som å ha et 0 på ti-plassene.

Iterasjon 3:

La oss gå videre til sifrene i hundrevis posisjon:

Etter denne iterasjonen ser matrisen ut som:

Og algoritmen stopper her, med alle elementene sortert.

4. Gjennomføring

La oss nå se på implementeringen.

void sort (int [] numbers) {int maximumNumber = findMaximumNumberIn (numbers); int numberOfDigits = calcnumberOfDigitsIn (maximumNumber); int placeValue = 1; while (numberOfDigits--> 0) {applyCountingSortOn (numbers, placeValue); placeValue * = 10; }}

Algoritmen fungerer ved å finne ut maksimalt antall i matrisen og deretter beregne lengden. Dette trinnet hjelper oss med å sikre at vi utfører underrutinen for hver stedverdi.

For eksempel i matrisen, [7, 37, 68, 123, 134, 221, 387, 468, 769], maksimalt antall er 769 og lengden er 3.

Så vi gjentar og bruker subrutinen tre ganger på sifrene i hver posisjon:

void applyCountingSortOn (int [] numbers, int placeValue) {int range = 10 // desimal system, tall fra 0-9 // ... // beregne frekvensen av sifre for (int i = 0; i <lengde; i ++ ) {int digit = (numbers [i] / placeValue)% range; frekvens [siffer] ++; } for (int i = 1; i = 0; i--) {int digit = (numbers [i] / placeValue)% range; sortedValues ​​[frekvens [siffer] - 1] = tall [i]; frekvens [siffer] -; } System.arraycopy (resultat, 0, tall, 0, lengde); }

I underrutinen har vi brukt radiksen (område) for å telle forekomsten av hvert siffer og øke frekvensen. Så hver søppel i området fra 0 til 9 vil ha en viss verdi basert på frekvensen av sifre. Vi bruker deretter frekvensen til å plassere hvert element i matrisen. Dette hjelper oss også med å minimere plassen som kreves for å sortere matrisen.

La oss nå teste metoden vår:

@Test offentlig ugyldighet gittUnsortedArray_whenRadixSort_thenArraySorted () {int [] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort (tall); int [] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals (numbersSorted, numbers); }

5. Radix-sortering mot tellesortering

I underrutinen er lengden på Frekvens array er 10 (0-9). I tilfelle Counting Sort bruker vi ikke område. Lengden på Frekvens array vil være det maksimale antallet i arrayet + 1. Så vi deler dem ikke i søppelbøtter, mens Radix Sort bruker søpplene til å sortere.

Å telle sortering er ganske effektivt når lengden på matrisen ikke er mye mindre enn den maksimale verdien i matrisen, mens Radix Sort tillater større verdier i matrisen.

6. Kompleksitet

Ytelsen til Radix Sort avhenger av den stabile sorteringsalgoritmen som er valgt for å sortere sifrene.

Her har vi brukt Radix Sort for å sortere en rekke n tall i basen b. I vårt tilfelle er basen 10. Vi har brukt Counting Sort d ganger hvor d står for antall sifre. Så tidskompleksiteten til Radix Sort blir O (d * (n + b)).

Romkompleksiteten er O (n + b) siden vi har brukt en variant av Counting Sort som en underrutine her.

7. Konklusjon

I denne artikkelen beskrev vi Radix-sorteringsalgoritmen og illustrerte hvordan du implementerer den.

Som vanlig er kodeimplementeringene tilgjengelig på Github.