Přehled algoritmů Razení Přehled algoritmů Merge sort Problém inverzí Razení haldou Prioritní fronty Counting Sort Radix Sort Bucket Sort 14. března 2016 1/71 Problém řazení Přehled algoritmů ■ je daná množina K nad kterou je definované úplné uspořádání ■ vstupem problému řazení je posloupnost A — (fci,..., kn) prvků z K ■ výstupem je posloupnost A! — (k[,..., k'n), která je takovou permutací posloupnosti A, že Vi, j, 1 < z < j < n, platí < o 14. března 2016 2 / 71 Přehled algoritmů Stabilní algoritmy a algoritmy in situ ■ prvky množiny K mohou být strukturované ■ řazení podle klíče ■ řazení se nazývá stabilní právě když zachovává vzájemné pořadí položek se stejným klíčem ■ prostorová složitost algoritmů řazení je protože samotná vstupní posloupnost má délku n ■ pro přesnější charakterizaci prostorové složitosti jednotlivých algoritmů uvažujeme tzv. extrasekvenční prostorovou složitost, do které nezapočítáváme paměť obsazenou vstupní posloupností ■ algoritmy, jejichž extrasekvenční složitost je konstantní, se nazývají in situ (in pláce) o 14. března 2016 3 / 71 Přehled algoritmů Přehled časová složitost časová složitost algoritmus v nej horším v průměrném případě případě řazení vkládáním 6(n2) 6(n2) řazení výběrem 6(n2) 6(n2) řazení sléváním 0(nlog n) 0(nlog n) řazení haldou 0(nlog n) 0(nlog n) řazení rozdělováním 6(n2) 0(nlog n) řazení počítáním Q(k + n) @(k + n) číslicové řazení Q(d(n + k)) Q(d(n + k)) přihrádkové řazení 6(n2) 6(n) o 14. března 2016 4 / 71 Přehled algoritmy založené na porovnávání prvků vkládáním, Insertion sort in situ, stabilní výběrem, Selection sort in situ, není stabilní sléváním, Merge sort asymptoticky časově optimální, není in situ, stabilní haldou, Heapsort asymptoticky časově optimální, in situ, není stabilní rozdělováním, Quicksort není časově optimální, extrasekvenční složitost a stabilita závisí od implementace (optimálně in situ, existují stabilní implementace), velmi dobrý v praxi (průměrná složitost je O(nlogn)) algoritmy, které získávají informace jinak než porovnáváním prvků počítáním, Counting sort vstupní prvky jsou z množiny {0,..., k} číslicové řazení, Radix sort zobecnění řazení počítáním přihrádkové řazení, Bucket sort vyžaduje znalost o pravděpodobnostním rozdělení čísel na vstupu o 14. března 2016 5 / Razení Řazení sléváním ■ Merge sort ■ Problém inverzí Razení haldou Prioritní fronty Counting Sort Radix Sort Bucket Sort Řazení sléváním Merge sort Řazení sléváním (Merge sort) Rozděl posloupnost na dvě stejně velké podposloupnosti Vyřeš obě podposloupnosti (rekurzivně) Kombinuj dvě seřazené podposloupnosti do jedné o 14. března 2016 7 / 71 Spojení dvou seřazených posloupností - Merge ■ otázkou je, jak spojit dvě seřazené posloupnosti do jedné, která bude seřazená ■ při slévání porovnáváme vedoucí prvky obou posloupností ■ menší z porovnávaných prvků přesuneme do výslední posloupnosti procedura Merge má 4 parametry pole A indexy p, r takové, že p < q < r předpokládáme, že posloupnosti A[p... q] a A[q + 1... r] jsou seřazené pro provedení výpočtu je posloupnost A[p... r] seřazená pro zjednodušení kódu používáme sentinel o 14. března 2016 8 / 71 8 9 10 li 12 13 14 15 16 17 A 2 4 5 7 1 2 3 6 1 2 /c 3 4 5 i 2 3 4 5 2 4 5 7 oo Ä 1 2 3 6 OO i (a) 3 8 9 10 11 12 13 14 15 16 17 A 1 2 5 7 1 2 3 6 1 2 3 4 k 5 i 2 3 4 5 2 4 5 7 OO R 1 2 3 6 OO (c) i 8 9 10 li 12 13 14 15 16 17 1 4 5 7 1 2 3 6 1 2 3 k 4 5 i 2 3 4 5 2 4 5 7 OO Ä 1 2 3 6 OO 3 8 9 10 11 12 13 14 15 16 17 1 2 2 7 1 2 3 6 i 2 3 4 5 /c i 2 3 4 5 2 4 5 7 OO R 1 2 3 6 OO (d) o 14. března 2016 9 /7 L L L 8 9 10 íl 12 13 14 15 16 17 A 1 2 2 3 1 2 3 6 1 2 3 4 5 k i 2 3 4 5 2 4 5 7 oo R 1 2 3 6 OO i (e) 3 8 9 10 11 12 13 14 15 16 17 A 1 2 2 3 4 5 3 6 i 2 3 4 5 i /c 2 3 4 5 2 4 5 7 OO Ä 1 2 3 6 OO i (a) 3 8 9 10 11 12 13 14 15 16 17 A 1 2 2 3 4 5 6 7 ... i 2 3 4 5 i 2 3 /c 4 5 2 4 5 7 OO Ä 1 2 3 6 OO (i) J L L 8 9 10 íl 12 13 14 15 16 17 A 1 2 2 3 4 2 3 6 1 2 3 4 5 /c i 2 3 4 5 2 4 5 7 OO R 1 2 3 6 OO i (/) 3 8 9 10 11 12 13 14 15 16 17 A 1 2 2 3 4 5 6 6 i 2 3 4 5 i 2 k 3 4 5 2 4 5 7 OO Ä 1 2 3 6 OO (h) 3 0 14. března 2016 10/7 Řazení sléváním Merge sort Merge Procedure Merge(A,p, q, r) i ni <(— q — p + 1 2 tí2 4— t — q s j/nechť L[l... n\ + 1] a R[l 4 for i = 1 to n\ do L[i 5 for j; = 1 to ri2 do i? [7 6 L[n\ + 1] oo 7 Íž[n2 + 1] an B v každé z podposloupnosti spočítáme inverze Q spočítáme inverze mezi prvky různých podposloupnosti ■ cílem je navrhnout algoritmus s lepší složitostí než je složitost naivního algoritmu ((9(n2)) ■ jestliže chceme, aby časová složitost algoritmu byla T(n) = O(nlogn), tak musí platit T(n) < 2T(n/2) + 0(n), tj. dekompozice a kompozice nesmí překročit lineární složitost ■ jak vyřešit kompozici (bod 3) v čase 0{n) ? o 14. března 2016 18 / 71 Řazení sléváním Problém inverzí Problém inverzí - kombinuj - pokus 1 otázka jak spočítat inverze (a, b) mezi prvky a bj, tak b j je v inverzi se všemi prvky a^,..., a& a proto k počtu inverzí připočteme k — i + 1 o 14. března 2016 20 / 71 zařazené prvky ■ inverze mezi prvky zařazenými do výsledné posloupnosti jsou již započítané ■ jestliže ai < bj, tak do výsledné posloupnosti přesuneme ai clí < bj < bj+i < bj+2 < • • • ai není v inverzi se žádným z bj, &7+1, • • • ■ jestliže ai > bj, tak do výsledné posloupnosti přesuneme bj bj < a{ < flfc+i < < • • • bj je v inverzi s každým z a^, a^+i, • • • o 14. března 2016 21 / 71 Algoritmus Merge_and_Count(A, B) 1 l fi p return (r, L) složitost algoritmu je T(n) = 2T(n/2) + 0(n) a proto T(n) = O(nlogn) o 14. března 2016 23 / 71 Razení I \ Cl III OI v Cl I 111 I I ■ Merge sort ■ Problém inverzí •v Q Razení haldou ■ Razení haldou ■ Prioritní fronty ■ Counting Sort ■ Radix Sort ■ Bucket Sort Razení haldou - Heapsort prvky posloupnosti vložíme do (binární) haldy ■ halda je datová struktura ■ pole ■ prvky pole odpovídají vrcholům binárního stromu ■ binární strom je úplný (vrcholy na všech úrovních s výjimkou předposlední mají právě dva následníky) a zleva zarovnaný (nejhlubší úroveň je zaplněná zleva doprava) ■ pole reprezentující haldu má dva atributy ■ A.length počet prvků v poli ■ A.heap_size počet prvků haldy uložených v poli ■ A[l... A.heap_size] obsahuje prvky haldy 14. března 2016 25 / Halda o 14. března 2016 26 / Halda kořen haldy je uložený v A[l pro daný index i vypočteme indexy následníků a předchůdce vrcholu A předpisem Parent(í) return [i/2\ Left(z) return 2i Right(z) return 2i + 1 o 14. března 2016 27 / 71 Halda - vlastnost haldy rozlišujeme minimovou a maximovou haldu v obou případech prvky (čísla) uložené v haldě musí splňovat vlastnost haldy pro každý vrchol maximové haldy platí, že hodnota uložená ve vrcholu je větší nebo rovna než hodnoty uložené v jeho následnících nej větší prvek haldy je uložený v její kořeni pro každý vrchol minimové haldy platí symetricky A[Parent(z)] < A[i výběr mezi minimovou a maximovou haldou závisí od kontextu: řazení od největšího resp. nejmenšího prvku, prioritní fronty, . ..) o 14. března 2016 28 / 71 Operace nad (maximovou) haldou ■ Max_Heapify garantuje platnost vlastnosti haldy, složitost O(logn) ■ Build_Max_Heap vybuduje z pole haldu, složitost 6(n) ■ Heapsort seřadí prvky pole, složitost O(nlogn) ■ procedury Max_Heap_Insert, Heap_Extract_Max , Heap_Increase_key a Heap_Maximum využijeme pro implementaci prioritní fronty o 14. března 2016 29 / 71 Obnovení vlastnosti haldy procedura Max_Heapify(A, i) predpokladá, že • binárni stromy s kořeny Left(z) a Right(z) jsou (maximové) haldy a že • prvek A[i] může být menší než jeho následníci, tj. nemusí splňovat vlastnost haldy procedura modifikuje A tak, že po její provedení strom s kořenem A[i] tvoří haldu úprava je založena na přesunu prvku A[i] směrem dolů o 14. března 2016 30 / 71 Max_Heapify Řazení haldou Razení haldou Max_Heapify(A, i) 1 I <— Left(z) 2 r <- Right(z) 3 if I < A.heapsize A A[l] > A 1 4 then largest A[largest] 7 then largest (n h=0 h=0 h=0 při zjednodušování výrazu jsme využili rovnost y h 1/2 ^o 2» (1 - 1/2)2 0 14. března 2016 37 / 71 Algoritmus řazení haldou, Heapsort použitím procedury Build_Max_Heap vybudujeme maximovou haldu nad polem A[l... n], kde n — A.length maximální prvek pole A je uložený v kořeni A[l] a proto ho můžeme přesunout na jeho finální pozici A[n] (vyměníme prvky A[l] a A[n]) prvek, který jsme přesunuli do kořene, může porušit vlastnost haldy a pro obnovení vlastnosti haldy použijeme Max_Heapify(A, 1) celý proces opakujeme pro haldu velikosti n — 1 Heapsort(A) 1 Build_Max_Heap(A) 2 for i — A.length downto 2 do vyměň A[l] a A 3 A.heapsize <(— A.heapsize — 1 4 Max_Heapify(A, 1) od o 14. března 2016 38 / 71 o 14. března 2016 39 / 71 Heapsort - složitost ■ procedura Build_Max_Heap má složitost 0{n) ■ každé z n — 1 volaní procedury Max_Heapify má složitost O(logn) ■ algoritmus Heapsort má složitost O(nlogn) o 14. března 2016 40 / 71 Řazení haldou Optimalizace a varianty Optimalizace a varianty ■ strom vyšší arity ■ ve vrcholu stromu uložených několik hodnot ■ budování haldy výměnou zdola nahoru halda je na začátku prázdná a postupně do ní vkládáme prvky vstupní posloupnosti; prvek vložíme na poslední místo (jako list) a v případě porušení vlastnosti haldy ho (rekurzivně) zaměníme s jeho rodičem; časová složitost vybudování haldy je O(nlogn) ■ bottom - up heapsort optimalizuje etapu seřazování prvků; maximální prvek z kořene si vymění místo s posledním prvkem haldy a pro obnovení vlastnosti haldy výměnami se postupuje zdola nahoru ■ Smoothsort (Edsger Dijkstra) - stejná asymptotická složitost, lepší chování pro vstupní posloupnosti, které jsou téměř uspořádané o 14. března 2016 41 / 71 Prioritní fronty ■ datová struktura pro reprezentaci množiny, nad prvky množiny je definováno uspořádání ■ umožňuje efektivní realizaci operací: Insert^, x) vloží prvek x do množiny S Maximum(S) vrátí největší prvek množiny S Extract_Max(S') odstraní z množiny S největší prvek Increase_Key(S', x, k) nahradí prvek x prvkem k za předpokladu, že k > x m alternativně můžeme definovat prioritní frontu vůči minimálnímu prvku ■ prioritní frontu implementujeme jako maximovou haldu o 14. března 2016 42 / 71 Maximum a Extract.Max ■ prvky množiny S tvoří haldu A m maximální prvek haldy je v jejím kořeni; jeho nalezení má konstantní složitost Heap_Maximum(A) i return A[l] ■ odstranění maximálního prvku se implementuje stejně jako v algoritmu řazení ■ složitost operace je O(logn) Heap_Extract_Max(A) 1 if A.heapsize < 1 then return prázdná fronta fi 2 max <(— A[l] s A[l] <(— A[A.heapsize] 4 A.heapsize <(— A.heapsize — 1 5 Max_Heapify(A, 1) 6 return max o 14. března 2016 43 / 71 Increase.Key ■ procedura Heap_Increase_Key implementuje operaci IncreaseJKey ■ index i identifikuje prvek, který má být operací nahrazen (navýšen) ■ nejdříve změníme hodnotu A[i] na novou hodnotu key a potom obnovíme vlastnost haldy Heap_lncrease_Key(A, z, key) 1 if key < A[i] then return nová hodnota je menší než původní fi 2 A[i] ^— key 3 while i > 1 A A[Parent(z)] < A[i] do 4 vyměň A[i] a A[Parent(z)] 5 i <— Parent(z) od složitost: O(logn) 14. března 2016 Insert ■ procedura Max_Heap_Insert implementuje operaci Insert ■ na konec pole vložíme nový prvek, který je menší než všechny ostatní prvky, symbolicky ho označujeme —oo ■ zvýšíme hodnotu vloženého prvku na hodnotu prvku, který chceme vložit do fronty Max_Heap_lnsert(A, key) 1 A.heapsize A.heapsize + 1 2 A[A.heapsize] i--oo s Heap_Increase_Key(A, A.heapsize, key) složitost: O(logn) 14. března 2016 45 / 71 Razení I \ Cl III OI v Cl I 111 I I ■ Merge sort ■ Problém inverzí ■ Razení haldou ■ Prioritní fronty □ Quicksort ■ Counting Sort ■ Radix Sort ■ Bucket Sort Quicksort Řazení rozdělováním - Quicksort Rozděl posloupnost A[p... r] na dvě podposloupnosti A[p... q — 1] a A[q ... r tak, aby všechny prvky v A[p... q — 1] byly menší nejvýše rovné prvkům v A[q ... r] Vyřeš obě posloupnosti (rekurzivně) seřaď Kombinuj protože obě podposloupnosti jsou seřazené, není nutný žádný další výpočet Mergesort Rozděl posloupnost na dvě posloupnosti poloviční velikosti. Vyřeš obě podposloupnosti (rekurzivně) seřaď Kombinuj spoj dvě seřazené podposloupnosti do jedné o 14. března 2016 47 / 71 Quicksort Quicksort ■ hlavní částí algoritmu je rozdělování posloupnosti do dvou posloupností požadovaných vlastností ■ při rozdělování využíváme pivota ■ každý prvek posloupnosti porovnáváme s pivotem ■ podposloupnosti prvků menších / větších než pivot o 14. března 2016 48 / 71 Quicksort Quicksort i p,j r (a) F 8 7 1 3 5 6 4 1 ■ i P, i 1 1 j ■ r (b) N 7 1 3 5 6 4 1 1 1 P, i ■ l ■ ■ j ■ r (c) 2 7 1 3 5 6 4 1 P, i ■ l l ■ 1 ■ j ■ r (d) 2 8 7 1 3 5 6 4 l V I i ■ l ■ i ■ j ■ r (e) 2 k 5 6 4 V ■ 3 r ■ (0 2 1 3 8 7 V l i ■ 1 ■ l J ■ ■ 1 r ■ (g) 2 1 3 8 7 5 V l i ■ 1 1 1 1 r ■ (h) 2 1 3 8 7 5 6 V l i ■ l ■ i 1 r ■ (i) 2 1 w VL 5 6 0 14. brezna 2016 49 / 71 Quicksort Quicksort^, p, r) 1 if p < r 2 then q <— Partition^, p, r) 3 Quicksort^, p, q - 1) 4 Quicksort^, q + 1, r) fi Partition(A,p, r) 1 pivot A[r 2 Í i— p — 1 3 for j; = p to r do 4 if A [j] < pz^oí then 5 č return i i <- i + 1 vyměň A [z] a A[j] f i od o 14. března 2016 50 / 71 Quicksort Korektnost chceme dokázať, že procedúra Partition vráti index i takový, že ■ A[i] = pivot ■ pro p < k < i platí A[k] < A[i ■ pro i < k < r platí A[k] > A[i Invariant cyklu na začátku každé iterace for cyklu v řádcích 3-6 platí pro každý index k □ jestliže p < k < i, tak A[k] < pivot jestliže i + l pivot Inicializace iniciální přiřazení je pivot ^— A[r], i^— p — laj^— p invariant (triviálně) platí 14. března 2016 51 / 71 Quicksort Korektnost Invariant cyklu na začátku každé iterace for cyklu v řádcích 3-6 platí pro každý index k □ jestliže p < k < i, tak A[k] < pivot jestliže i + l pivot Iterace A[j] > pivot - efektem iterace cyklu je zvýšení hodnoty j o 1; invariant platí A[j] < pivot - efektem iterace cyklu je zvýšení hodnoty i a výměna A[i] s A\j], to garantuje zachování platnosti podmínky 1 zachování platnosti podmínky 2 garantuje fakt, že jsme do A[j — 1] přesunuli prvek větší než pivot o 14. března 2016 52 / 71 Quicksort Korektnost Invariant cyklu na začátku každé iterace for cyklu v řádcích 3-6 platí pro každý index k □ jestliže p < k < i, tak A[k] < pivot jestliže i + l pivot Ukončení výpočet končí když j — r + 1, což spolu s faktem, že po posledním provedení iterace platí invariant, garantuje že pro p < k < i platí A[k] < A[i] a pro i A[i] v poslední iteraci je j — p, A[j] — pivot < pivot, provede se výměna A[i] s A[j] co garantuje, že po ukončení výpočtu cyklu platí A[i] — pivot o 14. března 2016 53 / 71 Quicksort Složitost složitost v nejhorším případě např. pro vstupní posloupnost, která je již seřazená, nebo která obsahuje stejné prvky T{n) = T{n - 1) + T(0) + 6(n) = T{n - 1) + 6(n) T(n) = G(n2) složitost v nejlepším případě nastává, když při každém rekurzivním volání rozdělí pivot posloupnost na dvě stejně velké podposloupnosti T{n) = 2T(n/2) + G(n) T{n) — O(nlogn) průměrná složitost T{n) — O(nlogn) o 14. března 2016 54 / 71 Quicksort Alternativní postup rozdělování I ■ postupujeme od obou konců posloupnosti až do chvíle, než jsou detekovány dva prvky, které jsou vůči sobě v opačném pořadí; prvky si vymění svou pozici ■ při tomto postupu se udělá průměrně 3 krát méně výměn ■ algoritmus není stabilní Hoare Partition(A,p, r) 1 x A[p] 2 Í i— p — 1 s j r + 1 4 while true do 5 6 7 repeat j; j; — 1 until A[j] < x od repeat i z + 1 until A[z] > x od if z < j then swapA[z] a A[j] else return j fi od 14. března 2016 55 / 71 Quicksort Alternativní postup rozdělování II ■ obě uvedené schémata se chovají špatně v případě, že ve vstupní posloupnosti se prvky opakují ■ rozdělovači schéma, které řeší posloupnosti s opakujícími se prvky ■ při rozdělování se hledají prvky menší než pivot a větší než pivot ■ prvky stejné jako pivot jsou již na své pozici ■ prvky menší (větší) než pivot se seřadí rekurzivně o 14. března 2016 56 / 71 Quicksort Iterativní verze Quicksortu algoritmus ve tvaru tail rekurze Tail Recursive Quicksort^, p, r) 1 while p < r do 2 q^r- Partition^, p, r) 3 Tail Recursive Quicksort^, p, q- I) 4 p p then stack.push((p, q — i))fi 8 \f q -\- 1 < r then stack.push((q + 1, r)) f i p od 14. března 2016 57 / 71 Quicksort Složitost problému řazení složitost řadících algoritmů založených na vzájemném porovnávání prvků posloupnosti je O(nlogn) □ búno vstupní posloupnost ai,..., an obsahuje vzájemně různé prvky B každé porovnání určí větší ze dvou prvků B výpočet algoritmu můžeme popsat rozhodovací stromem, jehož vnitřní vrcholy jsou označeny y porovnávaných prvků a mají dva syny odpovídající vztahu < a > □ výpočet na konkrétním vstupu představuje cestu v rozhodovacím stromě z kořene do listu; jeho složitost je úměrná délce cesty B každý list jednoznačně určuje seřazení a7r(i) < a7r(2) < • • • < air(n) vstupních prvků □ algoritmus musí mít možnost vypočítat každou možnou permutaci vstupních prvků B počet různých permutací je n\ B strom musí mít alespoň n\ listů ^> má hloubku alespoň log(n!) = O(nlogn) WSŘ 14. března 2016 58 / 71 Řazení v lineárním čase Razení ■ Merge sort ■ Problém inverzí ■ Razení haldou ■ Prioritní fronty B Řazení v lineárním čase ■ Counting Sort ■ Radix Sort ■ Bucket Sort o 14. března 2016 59 / 71 Řazení v lineárním čase Counting Sort Řazení počítáním - Counting Sort předpokládá, že vstupní posloupnost obsahuje celá čísla z intervalu 0... k, kde k je nějaké pevně dané přirozené číslo jestliže k — 0(ri), tak složitost řazení počítáním je Q(n) o 14. března 2016 60 / 71 Counting sort ■ vstupní posloupnost A[l... n ■ pole B[l.. .n] obsahuje seřazenou posloupnost ■ pole C[0... A:] se využívá v průběhu výpočtu ■ pro každou hodnotu i — 0,1,..., k spočítáme, kolik je ve vstupní posloupnosti čísel i, výsledný počet uložíme do C [i] ■ pro každou hodnotu i — 0,1,..., k spočítáme, kolik je ve vstupní posloupnosti čísel menších nebo rovných i, využijeme k tomu hodnoty napočítané v předcházejícím kroku a výsledný počet uložíme opět do C [i] ■ procházíme vstupní posloupnost od konce a každé číslo uložíme do B přímo na jeho pozici, která je určená počtem menších nebo rovných čísel; hodnoty v C průběžně aktualizujeme o 14. března 2016 61 / 71 Řazení v lineárním čase Counting Sort Counting sort i 2 3 4 5 6 7 8 A 2 5 3 0 2 3 0 3 0 i 2 3 4 5 C 2 0 2 3 0 1 C 2 2 4 7 7 8 B C 1 2 3 4 5 6 0 1 2 3 4 5 2 2 4 6 7 8 i 2 3 4 5 6 7 8 i 2 3 4 5 6 7 8 B 0 3 0 3 3 0 1 2 3 4 5 0 1 2 3 4 5 C 1 2 4 6 7 8 C 1 2 4 5 7 8 0 0 2 2 3 3 3 5 0 14. března 2016 62 / 71 Řazení v lineárním čase Counting Sort Counting_Sort(A, £>, k) 1 j/inicializace C[0 ... k] 2 for i = 0 to k do s C [i] <- 0 od 4 for j = 1 to A.length do 5 C[Ab1] lognj ■ pro r = [log nj je složitost je 0(6n/logn) ■ pro r > [logn\ je složitost je 0(6n/logn) ■ pro r < [logn\ hodnota výrazu (b/r) klesá a hodnota výrazu n + 2r zůstává 0(n) BM 14. března 2016 68 / 71 Řazení v lineárním čase Bucket Sort Přihrádkové řazení - Bucket Sort předpokládá, že ■ vstupní posloupnost obsahuje čísla z intervalu [0... 1) ■ čísla rovnoměrně pokrývají celý interval ■ interval [0... 1) rozdělíme na stejně velké podintervaly - koše ■ vstupní čísla rozdělíme dle jejich hodnoty do košů ■ seřadíme prvky v každém koši o 14. března 2016 69 / 71 o 14. března 2016 70 / 71 Bucket sort Bucket_Sort(A) B[0 ... n — 1] je nové pole 1 2 n A.length 3 for i — 0 to n — 1 do B prázdny seznam od 5 for i — 1 to n do 6 přidej A[i] do seznamu B n A od 7 for z = 0 to n — 1 do # seřaď prvky seznamu B [i] použitím řazení vkládáním od 9 spoj seznamy £>[0], £>[1],..., B[n — 1] do jednoho seznamu nechť ni označuje počet prvků v koši B složitost je T{n) = Q(n) + Y%=o 0{n\) očekávaná složitost je pro vstup s uniformně rozdělenými čísly 0(n) o 14. března 2016 71 / 71