Skip to main content.

Zaradenie a popis

Bucket sort je triediaci algoritmus, ktorý pracuje v čase O(n). Netriedi prvky porovnávaním, ale predpokladá, že všetky prípustné čísla sú generované náhodným procesom, ktorý prvky distribuje uniformne na intervale. Myšlienkou je rozdeliť pole na konečný počet podintervalov (bucketov) a následne je každý bucket usporiadať osobitne (použitím iného triediaceho algoritmu, alebo rekurzívnym volaním Bucket sortu). Bucket sort je zovšeobecnením triediaceho algoritmu Pigeonhole sort.

^ TOP

Myšlienka algoritmu

Bucket sort pracuje nasledovným spôsobom:
 1. Vytvorí sa pole veľkosti rozsahu hodnôt, reprezentujúce počiatočne prázdne buckety.
 2. Prechádza sa vstupným poľom sa vkladajú sa prvku do zodpovedajúcich bucketov.
 3. Utriedi sa každý neprázdny bucket.
 4. Vložia sa prvky z neprázdnych bucketov naspäť do pôvodného poľa.

^ TOP

Vizualizácia

Prvky sa vložia do jednotlivých bucketov.
Bucketsort
Usporiadajú sa v rámci bucketov.
Bucketsort
Iné zobrazenie priebehu algoritmu.
Bucketsort

^ TOP

Zápis algoritmu

    n  := length [A]
    For i := 1 to n do
        Insert A[i] into list B[nA[i]]
    For i := 0 to n-1 do
        Sort list B with Insertion sort
    Concatenate the lists B[0], B[1], . . B[n-1] together in order.
^ TOP

Vlastnosti algoritmu

Ak chceme aby mal Bucket sort časovú zložitosť O(n), musí každý bucket obsahovať (v ideálnom prípade) len jeden prvok. Ak toto nie je splnené, triedenie prvkov v rámci bucketu stojí ďalší čas. Preto je Bucket sort vhodný len na triedenie vstupov o ktorých predpokladáme vhodné rozloženie prvkov po celom intervale.
Triedenie je stabilné, ak je požitý pomocný triediaci algoritmus tiež stabilný.

^ TOP

Experimentovanie

Center for Automation Research, University of Maryland, USA
Vizualizácia Bucket sortu.
http://www.cfar.umd.edu/~goldman/sort/1.1/

Department of Computer Science and Engineering, Indian Institute of Technology Madras, India
Vizualizácia Bucket sortu.
http://www.cs.iitm.ernet.in/tell/foc_selfstudy/bucket_sort.htm

^ TOP