streamalism.org

1. Introduktion

I denne vejledning lærer vi om Radix Sort, analyserer dens ydeevne og ser på dens implementering.

Her fokuserer vi på at bruge Radix Sort til at sortere heltal, men det er ikke begrænset til kun tal. Vi kan bruge den til at sortere andre typer som f.eks Snor, også.

For at holde det enkelt vil vi fokusere på det decimalsystem, hvor tallene udtrykkes i base (radix) 10.

2. Algoritmeoversigt

Radix-sortering er en sorteringsalgoritme, der sorterer tal baseret på placeringen af ​​deres cifre. Dybest set bruger det stedværdien af ​​cifrene i et tal. I modsætning til de fleste af de andre sorteringsalgoritmer, såsom Flet sortering, Indsæt sortering, Boblesortering, sammenligner det ikke tallene.

Radix-sortering bruger en stabil sorteringsalgoritme som en underrutine til at sortere cifrene. Vi har brugt en variation af tællesortering som en underrutine her, der bruger radix til at sortere cifrene i hver position. Tællesortering er en stabil sorteringsalgoritme, og den fungerer godt i praksis.

Radix-sortering fungerer ved at sortere cifre fra det mindste signifikante ciffer (LSD) til det mest signifikante ciffer (MSD). Vi kan også implementere Radix-sortering for at behandle cifre fra MSD.

3. Et hurtigt eksempel

Lad os se, hvordan det fungerer med et eksempel. Lad os overveje følgende array:

Iteration 1:

Vi sorterer denne matrix ved at behandle cifre fra LSD og bevæge os mod MSD.

Så lad os starte med cifrene et sted:

Efter den første iteration ser arrayet nu ud som:

Bemærk, at numrene er sorteret efter cifrene et sted.

Iteration 2:

Lad os gå videre til cifrene ti gange:

Nu ser arrayet ud:

Vi ser, at tallet 7 har besat den første position i arrayet, da det ikke har noget ciffer i ti-pladsen. Vi kunne også tænke på dette som at have et 0 på ti-pladsen.

Iteration 3:

Lad os gå videre til cifrene i hundreder position:

Efter denne iteration ser arrayet ud som:

Og algoritmen stopper her med alle elementer sorteret.

4. Implementering

Lad os nu se på implementeringen.

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

Algoritmen fungerer ved at finde ud af det maksimale antal i arrayet og derefter beregne dets længde. Dette trin hjælper os med at sikre, at vi udfører underrutinen for hver stedværdi.

For eksempel i arrayet, [7, 37, 68, 123, 134, 221, 387, 468, 769], det maksimale antal er 769 og længden er 3.

Så vi gentager og anvender subrutinen tre gange på cifrene i hver position:

void applyCountingSortOn (int [] numbers, int placeValue) {int interval = 10 // decimal system, tal fra 0-9 // ... // beregne hyppigheden af ​​cifre for (int i = 0; i <længde; i ++ ) {int ciffer = (tal [i] / placeValue)% interval; frekvens [ciffer] ++; } for (int i = 1; i = 0; i--) {int ciffer = (tal [i] / placeValue)% interval; sortedValues ​​[frekvens [ciffer] - 1] = tal [i]; frekvens [ciffer] -; } System.arraycopy (resultat, 0, tal, 0, længde); }

I subrutinen har vi brugt radixen (rækkevidde) at tælle forekomsten af ​​hvert ciffer og øge dets frekvens. Så hver bakke i området fra 0 til 9 vil have en vis værdi baseret på cifrefrekvensen. Vi bruger derefter frekvensen til at placere hvert element i arrayet. Dette hjælper os også med at minimere den nødvendige plads til at sortere arrayet.

Lad os nu teste vores metode:

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

5. Radix Sort vs Counting Sort

I subrutinen er længden af frekvens array er 10 (0-9). I tilfælde af Counting Sort bruger vi ikke rækkevidde. Længden af frekvens array vil være det maksimale antal i arrayet + 1. Så vi deler dem ikke i skraldespande, mens Radix Sort bruger skraldespandene til at sortere.

Optælling af sortering er ret effektiv, når længden af ​​arrayet ikke er meget mindre end den maksimale værdi i arrayet, mens Radix Sort giver mulighed for større værdier i arrayet.

6. Kompleksitet

Udførelsen af ​​Radix Sort afhænger af den stabile sorteringsalgoritme, der er valgt til at sortere cifrene.

Her har vi brugt Radix Sort til at sortere en matrix af n tal i base b. I vores tilfælde er basen 10. Vi har anvendt Counting Sort d gange hvor d står for antallet af cifre. Så tidskompleksiteten af ​​Radix Sort bliver O (d * (n + b)).

Rumkompleksiteten er O (n + b) da vi her har brugt en variation af Counting Sort som en subrutine.

7. Konklusion

I denne artikel beskrev vi Radix-sorteringsalgoritmen og illustrerede, hvordan den implementeres.

Som normalt er kodeimplementeringerne tilgængelige på Github.