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.

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:

• 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 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

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ť

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:

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.