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 m je počet přihrádek, n 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

     /**
      * 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;
     }
 







Doporučujeme

Internet pro vaši firmu na míru