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