Radix sort – triedenie pomocou číselných rádov v Java

Triediace algoritmy sa používajú na vzostupné alebo zostupné preusporiadanie prvkov poľa alebo zoznamu podľa numerického alebo lexikografického poradia. Triedenie je veľmi dôležité pre optimálny výkon iných algoritmov, ktoré vyžadujú triedené vstupné dáta.

Existuje množstvo rozličných triediacich algoritmov. Výber vhodného algoritmu závisí na faktoroch ako veľkosť a vlastnosti vstupných dát, dostupná pamäť a požiadavky na časovú a priestorovú náročnosť.

Aby sme ti uľahčili výber, predstavíme si v našom seriáli postupne najznámejšie algoritmy triedenia dát, vysvetlíme si ich princípy, výhody a nevýhody a naprogramujeme si ich v Jave.

Dnes sa budeme venovať triedeniu pomocou rádov čísel (angl. Radix sort).

Doteraz sme sa venovali nasledujúcim triediacim algoritmom:

• Triediace algoritmy: úvod do triedenia dát,
• Bubble sort – bublinkové triedenie,
• Comb sort – hrebeňové triedenie,
• Big O notácia: analýza zložitosti algoritmov,
• Selection sort – triedenie výberom,
• Insertion sort – triedenie vkladaním,
• Counting sort – triedenie počítaním,
• Heap sort – triedenie haldou,
• Merge sort – triedenie delením a spájaním,
• Quick sort  – rýchle triedenie pomocou pivota,
• Bucket sort (bin sort) – triedenie pomocou vedier (košov).

Radix sort algoritmus

Radix sort je efektívny algoritmus triedenia pre čísla alebo reťazce s fixnou dĺžkou kľúčov. Patrí k algoritmom, ktoré nefungujú na princípe porovnávania, ale už ako naznačuje slovo radix (t. j. číselný rád) triedenie prebieha postupným spracovaním a triedením podľa jednotlivých číslic, resp. znakov.

Triedenie môže začať od konca reťazca, resp. čísla, to znamená od najmenej významnej číslice (LSD – least significant digit) alebo od začiatku, teda od najvýznamnejšej číslice (MSD – most significant digit), pri triedení sa využíva upravený počítací algoritmus (counting sort), ktorý sme si už predstavili. Vždy sa zotriedia čísla podľa jedného rádu a až potom sa pokračuje na ďalší, pričom sa berie ohľad na usporiadanie z predchádzajúceho kroku.

Aj keď sa história algoritmu datuje do roku 1887 a začiatkom 20. storočia sa používal na triedenie diernych štítkov, v súčasnosti sa stále využíva Binary MSD radix sort a rovnako sa používa v kombinácii s inými algoritmami v tzv. hybridných algoritmoch.

Radix sort  – princíp fungovania algoritmu

V našom príklade si ukážeme LSD. Táto forma radix sortu má výhodu oproti MSD, že algoritmus triedenia je stabilný.

Predtým ako začne samotné triedenie potrebujeme zistiť, aké je maximálne číslo v nezotriedenom vstupnom poli. Počet jeho číslic potom určuje počet prechodov, ktoré budú potrebné na úplne zotriedenie vstupu. Z nášho príkladu na obrázku je zrejmé, že maximálne číslo je 958 a počet prechodov je 3. Následne si už vyberieme typ radix triedenia (MSD alebo LSD).

Postupne prechádzame číslice na mieste jednotiek, desiatok, stoviek atď. Pomocou counting sortu zistíme početnosť jednotlivých číslic, ich indexy v zotriedenom výsledku a tie následne využijeme na preskupenie čísiel na vstupe tak, aby sme dostali zotriedené čísla na základe aktuálneho prechodu. Napr. po zotriedení čísel na mieste jednotiek (modrá tabuľka) si môžeme všimnúť, že čísla sú zotriedené a zároveň rovnaké čísla si stále zachovávajú relatívne poradie oproti vstupu (stabilita algoritmu). Zelená tabuľka ukazuje stav po zotriedení na základe desiatok a oranžová už konečný výsledok triedenia po zotriedení stovkového radixu. V našom príklade boli všetky čísla trojciferné. Ak by sme ale mali medzi nimi aj dvojciferné alebo jednociferné museli by sme k nim pristupovať tak, ako keby mali svoj číselný prefix vyplnený nulami.

Radix sort – animácia, vizualizácia

Výhody algoritmu Radix sort

• Rýchly, ak sú kľúče krátke a z relatívne úzkeho pásma.
• Vhodný aj na triedenie znakov v reťazcoch (string).
• LSD forma je vždy stabilná, MSD sa dá upraviť na stabilný algoritmus.
• Dá sa paralelizovať a rozložiť tak výpočtovú záťaž na viac procesorov.

Nevýhody algoritmu Radix sort

• Vyžaduje si extra pamäťový priestor.
• Je málo flexibilný, musí sa upraviť pre rôzne dátové typy.

Radix sort – časová náročnosť

Na tejto stránke si môžeš prejsť jednotlivými krokmi algoritmu, vďaka čomu si vieš overiť časovú náročnosť algoritmu.

Radix Sort – implementácia, Java kód

Teraz si ukážeme implementáciu algoritmu Radix sort (verzia LSD) v Jave.

RadixSort.java

package sorting;

public class RadixSort {
    private final int BASE = 10; // digits [0-9]

    int getMaxElement(int[] data) {
        int max = data[0];
        for (int i = 1; i < data.length; i++)
            if (data[i] > max)
                max = data[i];
        return max;
    }

    public void sort(int[] data)
    {
        // Get maximum element
        int max = getMaxElement(data);
        // Apply counting sort to sort elements based on radix value
        for (int radix = 1; max / radix > 0; radix *= BASE)
            radixCountingSort(data, radix);
    }

    void radixCountingSort(int[] data, int radix) {
        int[] output = new int[data.length + 1];
        int[] count = new int[BASE];
        // Calculate count of elements
        for (int i = 0; i < data.length; i++)
            count[(data[i] / radix) % BASE]++;
        // Calculate cumulative count
        for (int i = 1; i < BASE; i++)
            count[i] += count[i - 1];
        // Place the elements in sorted radix order
        for (int i = data.length - 1; i >= 0; i--) {
            output[count[(data[i] / radix) % BASE] - 1] = data[i];
            count[(data[i] / radix) % BASE]--;
        }
        // Copy array from output back to data
        System.arraycopy(output, 0, data, 0, data.length);
        System.out.print("Radix: " + radix + " -> ");
        printArray(data);
    }

    // Function to print an array
    public void printArray(int[] data)
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

Main.java

import sorting.RadixSort;

public class Main {
    public static void main(String[] args) {
        int[] dataToSort = { 165, 958, 635, 694, 480, 637, 5, 598, 82};
        RadixSort radixSort = new RadixSort();
        System.out.print("Input: ");
        radixSort.printArray(dataToSort);
        radixSort.sort(dataToSort);
        System.out.print("Sorted: ");
        radixSort.printArray(dataToSort);
    }
}

Výstup z tohto príkladu je:

Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si kód Java RadixSort.

O autorovi

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.