streamalism.org

1. Úvod

V tomto tutoriáli sa dozvieme niečo o Radix Sort, analyzujeme jeho výkon a pozrieme sa na jeho implementáciu.

Tu sa zameriavame na použitie Radix Sort na triedenie celých čísel, ale neobmedzuje sa iba na čísla. Môžeme ho použiť na triedenie ďalších typov ako napr Reťazec, tiež.

Kvôli zjednodušeniu sa zameriame na desatinnú sústavu, v ktorej sú čísla vyjadrené v základe (radix) 10.

2. Prehľad algoritmov

Radix sort je triediaci algoritmus, ktorý triedi čísla na základe pozícií ich číslic. V zásade používa miestnu hodnotu číslic v čísle. Na rozdiel od väčšiny ostatných algoritmov triedenia, napríklad Merge Sort, Insertion Sort, Bubble Sort, čísla sa neporovnávajú.

Radix sort používa stabilný algoritmus triedenia ako podprogram na triedenie číslic. Použili sme variáciu počítania triedenia ako podprogram, ktorý pomocou radixu triedi číslice na každej pozícii. Počítanie triedenia je stabilný algoritmus triedenia a v praxi funguje dobre.

Radixové radenie funguje tak, že sa číslice číslujú od najmenej významnej číslice (LSD) po najvýznamnejšiu číslicu (MSD). Môžeme tiež implementovať Radix sort na spracovanie číslic z MSD.

3. Rýchly príklad

Pozrime sa, ako to funguje na príklade. Uvažujme o nasledujúcom poli:

Iterácia 1:

Toto pole triedime spracovaním číslic z LSD a smerom k MSD.

Začnime teda s číslicami na jednom mieste:

Po prvej iterácii pole teraz vyzerá takto:

Upozorňujeme, že čísla boli zoradené podľa číslic na jednom mieste.

Iterácia 2:

Prejdime k čísliciam na desiatkach miest:

Teraz pole vyzerá takto:

Vidíme, že číslo 7 obsadilo prvú pozíciu v poli, pretože na mieste desiatok nemá žiadnu číslicu. Mohli by sme o tom uvažovať aj tak, že na mieste desiatok bude mať 0.

Iterácia 3:

Prejdime k čísliciam v stovke:

Po tejto iterácii pole vyzerá takto:

A tu sa algoritmus zastaví, pričom sú zoradené všetky prvky.

4. Implementácia

Pozrime sa teraz na implementáciu.

void sort (int [] cisla) {int maximumNumber = findMaximumNumberIn (numbers); int numberOfDigits = vypočítaťNumberOfDigitsIn (maximumčíslo); int placeValue = 1; while (numberOfDigits -> 0) {applyCountingSortOn (numbers, placeValue); placeValue * = 10; }}

Algoritmus pracuje tak, že zistí maximálny počet v poli a potom vypočíta jeho dĺžku. Tento krok nám pomáha zabezpečiť, aby sme vykonali podprogram pre každú miestnu hodnotu.

Napríklad v poli [7, 37, 68, 123, 134, 221, 387, 468, 769], maximálny počet je 769 a jeho dĺžka sú 3.

Takže iterujeme a aplikujeme podprogram trikrát na číslice v každej polohe:

void applyCountingSortOn (int [] numbers, int placeValue) {int range = 10 // decimal system, numbers from 0-9 // ... // vypočítať frekvenciu číslic pre (int i = 0; i <dĺžka; i ++ ) {int digit = (numbers [i] / placeValue)% range; frekvencia [číslica] ++; } pre (int i = 1; i = 0; i--) {int digit = (numbers [i] / placeValue)% range; triedenéHodnoty [frekvencia [číslica] - 1] = čísla [i]; frekvencia [číslica] -; } System.arraycopy (výsledok, 0, čísla, 0, dĺžka); }

V podprogramu sme použili radix (rozsah) počítať výskyt každej číslice a zvyšovať jej frekvenciu. Takže každý kôš v rozsahu od 0 do 9 bude mať určitú hodnotu založenú na frekvencii číslic. Potom pomocou frekvencie umiestnime každý prvok v poli. To nám tiež pomáha minimalizovať priestor potrebný na triedenie poľa.

Teraz otestujme našu metódu:

@Test public void givenUnsortedArray_whenRadixSort_thenArraySorted () {int [] čísla = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort (čísla); int [] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals (numbersSorted, numbers); }

5. Radix Radenie vs Počítanie Radenie

V podprogramu je dĺžka frekvencia pole je 10 (0-9). V prípade počítania zoradenia nepoužívame rozsah. Dĺžka frekvencia pole bude maximálny počet v poli + 1. Takže ich nerozdeľujeme na koše, zatiaľ čo Radix Sort používa koše na triedenie.

Počítanie zoradenia je celkom efektívne, keď dĺžka poľa nie je oveľa menšia ako maximálna hodnota v poli, zatiaľ čo Radix Sort umožňuje väčšie hodnoty v poli.

6. Zložitosť

Výkonnosť Radix Sort závisí od stabilného algoritmu triedenia zvoleného na triedenie číslic.

Tu sme použili Radix Sort na triedenie poľa n čísla v základe b. V našom prípade je základňa 10. Použili sme počítanie zoradenia d časy kde d znamená počet číslic. Časová zložitosť Radix Sort sa teda stáva O (d * (n + b)).

Priestorová zložitosť je O (n + b) pretože sme tu použili variáciu Counting Sort ako podprogram.

7. Záver

V tomto článku sme popísali Radixov algoritmus triedenia a objasnili, ako ho implementovať.

Implementácie kódu sú ako obvykle dostupné na serveri Github.