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 , kde
je počet přihrádek,
je velikost vstupního pole a
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ý 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; }
SEO od společnosti Digital Pylon
Online casino s algoritmem
České casino online online slot-vegas.cz
Hrajte nejlepší hry jako je GoodGame Empire.
Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?, Čeká vás pracovní pohovor mimo město? Podívejte se, jak dokonale zvládnout včasný příchod, 5 úžasných technologií ze světa hazardních her, Mirror and access to Mostbet, Svou kancelář můžete mít stále po ruce, Jaké výhody má digitalizovaná firma oproti off-line konkurenci?, Jaký systém vybrat pro snadné řízení výroby?, Nahradí umělá inteligence ajťáky?, Důvody, proč používat SnapTik ke stahování videí TikTok, Dokonalý den na pláži: Co si vzít s sebou, aby byl výlet zábavný a bezpečný?, Jak přežít dlouhý let?, Go pay GoodGame Empire, Blockchain, Rozhovor