Bucket sort

Bucket sort (bin sort) je stabilní řadicí algoritmus založení na rozdělení vstupního pole do několika částí – takzvaných bucketů (přihrádek) – a seřazení těchto částí pomocí jiného stabilního řadicího algoritmu.

Princip

Bucket sort nejprve rozdělí vstupní pole do několika (disjunktních) přihrádek. Každá přihrádka reprezentuje určitý rozsah vstupních dat – data by měla být v optimálním případě rovnoměrně rozdělena, aby nedocházelo k situaci, kdy je jedna přihrádka přeplněna a další je prázdná. V druhé fázi pak bucket sort zavolá na každou z přihrádek stabilní řadicí algoritmus, případně rekurzivně sám sebe (bucket sort degeneruje na counting sort v případě, že je počet přihrádek stejný jako rozsah dat). Nakonec algoritmus nakopíruje postupně všechny seřazené přihrádky do výstupního pole. Připomeňme si, že pole je seřazeno, protože každá přihrádka pokrývala určitý rozsah a rozsahy se nepřekrývaly.

Asymptotická složitost bucket sortu je $O(m \\cdot C(n/m))$ , kde je počet přihrádek, je velikost vstupního pole a C(x) je složitost vnitřního řadicího algoritmu.

Využití

Bucket sort se dá využít pro řazení obrovských dat, která by nemohl načíst klasický $O(n \\cdot \\log(n))$ algoritmus najednou. Algoritmus rozdělí vstupní data do dostatečně malých přihrádek a tyto postupně řadí v paměti, zatímco neaktivní přihrádky nechává uložené ve vnější paměti (např. pevný disk). Dalším scénářem využití bucket sortu je distribuované řazení, při kterém je každá přihrádka řazena v jiném vlákně, připadně dokonce na jiném stroji.

Kód

Java

     /**
      * Bucket sort
      * @param array pole k serazeni
      * @param bucketCount pocet bucketu
      * @return serazene pole (od nejmensiho k nejvyssimu)
      */
     public static int[] bucketSort(int[] array, int bucketCount) {
         if (bucketCount <= 0) throw new IllegalArgumentException("Neplatny pocet bucketu");
         if (array.length <= 1) return array; //trivialne serazeno
 
         int high = array[0];
         int low = array[0];
         for (int i = 1; i < array.length; i++) { //najdeme nejvyssi a nejnizsi
             if (array[i] > high) high = array[i];
             if (array[i] < low) low = array[i];
         }
         double interval = ((double)(high - low + 1))/bucketCount; //pocet cisel krytych jednim bucketem = pocet_cisel_celkem/pocet_bucketu
 
         ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
         for (int i = 0; i < bucketCount; i++) { //inicializace bucketu
             buckets[i] = new ArrayList();
         }
 
         for (int i = 0; i < array.length; i++) { //rozhozeni cisel do bucketu
             buckets[(int)((array[i] - low)/interval)].add(array[i]);
         }
 
         int pointer = 0;
         for (int i = 0; i < buckets.length; i++) {
             Collections.sort(buckets[i]); //mergeSort
             for (int j = 0; j < buckets[i].size(); j++) { //sesypat zpet
                 array[pointer] = buckets[i].get(j);
                 pointer++;
             }
         }
         return array;
     }

Princip

Využití

Kód

Doporučujeme