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.

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:

• 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

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ť

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:

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:

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.