Bucket sort (bin sort) – triedenie pomocou vedier (košov) 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.

Bucket sort algoritmus Java príklad
Bucket sort algoritmus Java príklad

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ť rýchlemu triedeniu pomocou vedier (angl. Bucket sort), známy tiež aj ako Bin sort.

    Doteraz sme sa venovali nasledujúcim triediacim algoritmom:

    Bucket sort, Bin sort algoritmus

    Bucket (Bin) sort je špeciálna triediaca technika, ktorá spočíva v rozdelení prvkov vstupného vektora do rôznych skupín (vedierok, resp. košov). Tieto skupiny sú vytvorené na základe rovnomerného rozdelenia (pozri aj Uniform distribution). Následne sú skupiny individuálne zotriedené ľubovoľných triediacim algoritmom a výstupný zotriedený výstup predstavuje spojenie výsledkov jednotlivých košov. Výpočtová zložitosť algoritmu potom závisí na algoritme, ktorý triedi dáta v každej skupine, počte skupín, ako aj na rovnomernom rozloženiu hodnôt na vstupe.

    Bucket sort, Bin sort – princíp fungovania algoritmu

    Ak musíme roztriediť veľké množstvo dát, ktoré majú tú vlastnosť, že sú rovnomerné roztriedené (napr. čísla objednávok), ich rozdelením do podskupín vieme zredukovať množstvo vzájomných porovnávaní medzi elementami, čo nám pomôže skrátiť čas triedenia. Po roztriedení dát ich môžeme udržiavať zotriedené v jednotlivých skupinách a pri pridávaní nových prvkov do skupín triediť iba tie, do ktorých pribudol nový prvok. Zotriedené dáta sa tiež jednoduchšie a rýchlejšie zotriedia, ak použijeme na to vhodný algoritmus, ako napr. Insertion sort. Rozdelenie do viacerých skupín nám zároveň umožní nasadiť techniky paralelného triedenia a spracovania dát.

    Základný princíp algoritmu Bucket sort je nasledovný:

    1. Určenie množstva vedier Jednorazovým prejdením cez hodnoty vieme určiť maximálnu hodnotu
    2. Vytvorenie poľa počiatočných prázdnych vedier
    3. Rozdistribuovanie prvkov do zodpovedajúcich vedier
      Najvhodnejšie je rozptýlenie elementov (scatter) pomocou jednoduchej hashovacej funkcie.
    4. Zotriedenie prvkov každého vedra
    5. Zozbieranie (gather) výsledkov z jednotlivých vedier v správnom poradí

    Bucket sort animácie, vizualizácia

    Vizuálne znázornenie algoritmu Bucket-Sort.
    Vizuálne znázornenie algoritmu Bucket-Sort.

    Výhody algoritmu Bucket sort

    • Pomerne efektívny pre dáta s rovnomerným rozdelením: desatinné čísla s rozsahom 0.0 až 1.0, resp. celé čísla v úzkom rozsahu.
    • Stabilný, ak sa použije stabilný triediaci algoritmus na triedenie dát u skupín.
    • Dá sa paralelizovať a rozložiť tak výpočtovú záťaž na viac procesorov.

    Nevýhody algoritmu Bucket sort

    • Vyžaduje dodatočný pamäťový priestor pre vytvorenie skupín.
    • Nevhodne zvolená rozptylová funkcia môže výrazne navýšiť časovú zložitosť.

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

    Algoritmus Metóda Časová náročnosť Pamäť Stabilný
    najhoršia priemer najlepšia
    Bucket sort Distribúcia O(n²) O(n + k) O(n + k) O(n + k) áno/nie

    Premenná n = počet elementov poľa, k = počet vedier

    Najhorší prípad časovej komplexity bucket sortu

    V najhoršom scenári skončia všetky prvky v rovnakom vedre v opačnom poradí. Môže to byť následok nevhodného rozloženia dát pre tento algoritmus, resp. nesprávne implementovanej rozptylovej funkcie. V takom prípade sa časová zložitosť blíži k O(n²).

    Bucket Sort – implementácia, Java kód

    Teraz si ukážeme implementáciu algoritmu Bucket sort v Jave.

    BucketSort.java

    package sorting;
    
    import java.util.ArrayList;
    import java.util.Collections;
    
    public class BucketSort {
        public void sort(float[] data)
        {
            // Set optimal bucket count here
            int bucketCount = 10;
            ArrayList<Float>[] buckets = new ArrayList[bucketCount];
    
            // Create empty buckets
            for (int i = 0; i < bucketCount; i++) {
                buckets[i] = new ArrayList<>();
            }
    
            // Scatter elements into buckets using appropriate hash function
            for (float f : data) {
                int bucketIndex = (int) Math.floor(f * 10);
                buckets[bucketIndex].add(f);
            }
    
            System.out.println("After distribution:");
            for (int i = 0; i < bucketCount; i++) {
                printBucket(i, buckets[i]);
            }
    
            // Sort all the buckets
            for (int i = 0; i < bucketCount; i++) {
                Collections.sort(buckets[i]);
            }
    
            System.out.println("After sorting individual buckets:");
            for (int i = 0; i < bucketCount; i++) {
                printBucket(i, buckets[i]);
            }
    
            // Concatenate buckets elements to get sorted data
            int j = 0;
            for (int i = 0; i < bucketCount; i++) {
                for (float num : buckets[i]) {
                    data[j++] = num;
                }
            }
        }
    
        public void printBucket(int id, ArrayList<Float> data)
        {
            System.out.println("Bucket " + id + " -> " + data);
        }
    
        // Function to print an array
        public void printArray(float[] data)
        {
            for (int i = 0; i < data.length; i++)
                System.out.print(data[i] + " ");
        }
    }

    Main.java

    import sorting.BucketSort;
    
    public class Main {
        public static void main(String[] args) {
            float[] dataToSort = { 0.88f, 0.16f, 0.39f, 0.26f, 0.82f, 0.94f, 0.21f, 0.12f, 0.23f, 0.68f };
            BucketSort bucketSort = new BucketSort();
            System.out.print("Input: ");
            bucketSort.printArray(dataToSort);
            System.out.println();
            bucketSort.sort(dataToSort);
            System.out.print("Sorted: ");
            bucketSort.printArray(dataToSort);
        }
    }

    Výstup z tohto príkladu je:

    Bucket Sort – implementácia, 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 BucketSort.

    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ť