Counting sort – triedenie počítaním 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.

Triedenie počítaním -counting sort
Triedenie počítaním -counting sort

V článku sa dozvieš:

    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 počítaním (angl. counting sort).

    Doteraz sme sa venovali nasledujúcim triediacim algoritmom:

    Counting sort

    Doteraz sme sa venovali algoritmom, ktoré porovnávali medzi sebou prvky a na základe toho vytvorili zotriedený výstup. Dnes si predstavíme prvý algoritmus, ktorý nepoužíva vo svojom základe porovnávanie.

    Counting sort je celočíselný stabilný triediaci algoritmus, ktorý je založený na počítaní objektov s odlišnými hodnotami kľúčov, z ktorých sa určuje pozícia vo výstupnej sekvencii. Je vhodné ho používať iba v situáciách, kedy rozptyl maximálnej a minimálnej hodnoty kľúčov je pomerne malý v porovnaní s počtom prvkom na vstupe. Tento algoritmus sa často využíva ako pomocná rutina v radix sorte.

    Counting sort algoritmus – princíp fungovania

    Counting sort algoritmus je vhodný ak máme veľa prvkov s celočíselnými kľúčmi, ktoré sa ideálne opakujú z pomerne malého rozsahu (max – min), potom môžeme aplikovať na zotriedenie vstupu prvkov tento pomerne efektívny algoritmus. Ten funguje na princípe počítania výskytu jednotlivých kľúčov, ktoré ukladá do pomocného poľa. To sa potom transformuje na pole indexov s výslednými pozíciami jednotlivých prvkov. Potom sa už pomocou neho premapujú prvky zo vstupného vektoru do výstupného.

    Najlepšie princíp fungovania algoritmu pochopíme na praktickom príklade v Jave, ktorý si implementujeme.

    Výhody algoritmu Counting sort

    • Jednoduchý na implementovanie,
    • rýchly a efektívny, ak rozsah kje v porovnaní s počtom prvkov na vstupe n malý,
    • stabilný.

    Nevýhody algoritmu Counting sort

    • Funguje len pre kľúče s celými číslami,
    • neefektívny pre veľký rozsah

    Counting sort časová náročnosť

    Algoritmus Metóda Časová náročnosť Pamäť Stabilný
    najhoršia priemer najlepšia
    Counting sort počítanie O(n+k) O(n+k) O(n+k) O(k) áno

    Premenná k je počet prvkov počítacieho pomocného poľa, matematicky k = (maximum – minimum + 1). Keďže iterujeme cez vstupné pole prvkov dostaneme časovú zložitosť O(n). Iterovanie cez pomocné pole prispieva ku komplexite O(k), takže celková časová zložitosť je spolu O(n+k).

    Uloženie k prvkov v pomocnom poli v pamäti má za následok priestorovú zložitosť O(k).

    Counting sort animácie, vizualizácia, gif

    Vizualizácia Counting sort vyzerá nasledovne:

    counting sort visualization
    SimonWaldherr, CC BY-SA 4.0, via Wikimedia Commons

    Zdroj: https://commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

    Animáciu algoritmu Counting sort nájdeš napríklad aj na tejto stránke.

    Counting sort Java implementácia

    Teraz si ukážeme jednoduchú implementáciu algoritmu Counting sort v Jave.

    CountingSort.java

    package sorting;
    
    public class CountingSort {
        private int min, max;
    
        public void sort(int data[])
        {
            // Don't sort if there are no elements
            if(data.length == 0)
                return;
    
            // Create ouput array
            int[] output = new int[data.length];
    
            // Find min and max value in 1 loop
            min = data[0];
            max = data[0];
            for (int i = 1; i < data.length; i++) {
                if (data[i] < min) {
                    min = data[i];
                } else if (data[i] > max) {
                    max = data[i];
                }
            }
    
            // Create count array
            int k = max - min + 1;
            int[] count = new int[k];
            System.out.println("min = " + min + ", max = " + max +
                    ", size (n) = " + data.length + ", range (k) = " + k);
    
            // Count occurrences of elements
            for (int i = 0; i < data.length; i++) {
                count[data[i] - min]++;
            }
            System.out.print("Count array: ");
            printArray(count);
    
            // Transform counts to positions
            for (int i = 1; i < count.length; i++) {
                count[i] += count[i - 1];
            }
            System.out.print("Transformed count array: ");
            printArray(count);
    
            // Map the elements from input to output based on count indexes
            // Do it backwards
            for (int i = data.length - 1; i >= 0; i--) {
                output[count[data[i] - min] - 1] = data[i];
                count[data[i] - min]--;
            }
    
            // Copy the elements from output back to original array
            for (int i = 0; i < data.length; i++) {
                data[i] = output[i];
            }
        }
    
        // 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();
        }
    }

    Algoritmus pozostáva z nasledujúcich krokov, ktoré si stručne vysvetlíme:

    Kontrola prázdneho poľa

    Ak je pole prázdne, nie je čo triediť.

    Nájdenie minimálnej a maximálnej hodnoty

    Zistime rozsah hodnôt min a max.

    Vytvorenie a inicializácia počítacieho poľa

    Veľkosť poľa count je rozdiel medzi maximálnou a minimálnou hodnotou plus jedna, aby pokrylo celý rozsah hodnôt.

    Spočítanie výskytov prvkov

    Pre každý prvok vo vstupnom poli sa zvýši hodnota na zodpovedajúcom indexe v počítacom poli o jeden.

    Transformácia na akumulované počty

    Každý prvok v počítacom poli sa aktualizuje na súčet všetkých predchádzajúcich hodnôt, čo určuje konečné pozície prvkov vo výstupnom poli.

    Umiestnenie prvkov do výstupného poľa

    Vstupné pole sa prechádza odzadu (kvôli zabezpečeniu stability) a prvky sa umiestňujú do výstupného poľa na základe hodnôt v počítacom poli, pričom po každom umiestnení prvku index v počítacom poli znížime o 1.

    Skopírovanie výstupu späť do pôvodného poľa

    Utriedené prvky z výstupného poľa sa skopírujú späť do pôvodného poľa.

    Main.java

    import sorting.CountingSort;
    
    public class Main {
        public static void main(String[] args) {
            int dataToSort[] = { 4, 2, 4, 2, 1, 1, 1, 7, 6, 3, 5, 5 };
            CountingSort countingSort = new CountingSort();
            System.out.print("Input: ");
            countingSort.printArray(dataToSort);
            countingSort.sort(dataToSort);
            System.out.print("Sorted: ");
            countingSort.printArray(dataToSort);
        }
    }

    Výstup z tohto príkladu je:

    výstup z príkladu triedenie počítaním

    Counting sort  –  Java kód

    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 Counting Sort.

    Ak si Java programátor a hľadáš prácu, pozri si naše benefity pre zamestnancov a reaguj na najnovšie ponuky práce.

    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.

    Daj nám o sebe vedieť