Třídící algoritmy. Insert Sort. Bubble Sort. Select Sort. Shell Sort. Quick Sort. Merge Sort. Heap Sort

Tˇrídící algoritmy. Insert Sort. Bubble Sort. Select Sort. Shell Sort. Quick Sort. Merge Sort. Heap Sort.

Tomáš Bayer | [email protected] ˇ Katedra aplikované geoinformatiky a kartografie, Pˇrírodovedecká fakulta UK.

ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

1 / 66

Obsah pˇrednášky 1

ˇ Vybrané tˇrídící algoritmy a jejich delení

2

ˇ pˇrímým vkládáním Tˇrídení

3

ˇ binárním vkládáním Tˇrídení

4

ˇ Bublinkové tˇrídení

5

ˇ pˇrímým výberem ˇ Tˇrídení

6

ˇ se zmenšujícím se krokem Tˇrídení

7

QuickSort

8

ˇ sléváním Tˇrídení

9

ˇ haldou Halda a tˇrídení

10

Pˇrehled tˇrídících algoritmu˚


2 / 66


ˇ 1. Tˇrídení: Postup, pˇri kterém uspoˇrádáváme vzestupneˇ nebo sestupneˇ prvky zadané posloupnosti X , X = {x1 , ..., xn },n... poˇcet prvku. ˚ ˇ se jedná o posloupnost cˇ ísel, všechny prvky stejného Nejˇcasteji datového typu. ˇ Vzestupné setˇrídení: Pro ∀xi ∈ X ⇒xi ≤ xi+1 ,i ∈ h0, n − 2i. ˇ Sestupné setˇrídení: Pro ∀xi ∈ X ⇒xi ≥ xi+1 ,i ∈ h0, n − 2i. ˇ ˇ za sestupné: prohození znaménka < za Zámena vzestupného tˇrídení > v tˇrídícím algoritmu. ˇ Duvod ˚ tˇrídení: ˇ operací s nimi. Snaha o uspoˇrádání dat a zefektivnení ˇ ˇ ˇradu operací efektivneji ˇ (tj. s Nad setˇrídenými daty lze navíc provádet ˇ ˇ nižší cˇ asovou i pamet’ovou složitostí) než nad nesetˇrídenými daty, ˇ Tomáš Bayer [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.) 3 / 66 napˇ r. | vyhledávací algoritmy.


ˇ 2. Delení tˇrídících algoritmu: ˚ Dveˇ skupiny tˇrídících algoritmu: ˚ vnitˇrní tˇrídící algoritmy ˇ ˇ poˇcítaˇce. Prvky tˇrídené posloupnosti nacházejí uvnitˇr pameti K jednotlivým prvkum ˚ posloupnosti lze pˇristupovat v libovolném poˇradí, Poˇcet prvku˚ n pˇredem znám. ˇ tˇrídící algoritmy vnejší ˇ Data uložena na nejakém periferním zaˇrízení. Poˇcet prvku˚ posloupnosti není znám pˇredem, k prvkum ˚ lze ˇ pˇristupovat pouze sekvenˇcne. ˇ poˇcítaˇce. Rozsáhlá data, která se nevejdou do pameti ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

4 / 66


3. Efektivita tˇrídících algoritmu: ˚ Kritéria efektivity tˇrídících algoritmu: ˚ ˇ posloupnosti, poˇcet pˇresunu˚ prvku˚ nutný k setˇrídení ˇ posloupnosti. poˇcet porovnání prvku˚ nutný k setˇrídení ˇ Nárocnost kroku: ˚ Oba kroky mají ruznou ˚ nároˇcnost. ˇ než jeho porovnání s jiným prvkem (3 Pˇresun prvku je výpoˇcetneˇ nároˇcnejší operace vs 1 operace). ˇ Minimalizace množství pˇresunu˚ pˇri tˇrídení. ˇ provádet ˇ pˇresuny prvku˚ na vetší ˇ vzdálenosti: jeden posun o n Efektivnejší ˇ než n posunu˚ o 1 prvek. prvku˚ výhodnejší ˇ Casová složitost tˇrídících algoritmu: ˚ Nejpomalejší algoritmy dosahují odhadu složitosti O(N 2 ), nejrychlejší O(N log N). ˇ nelze dosáhnout, neexistuje tedy algoritmus s Nižší složitosti pˇri tˇrídení odhadem složitosti O(N). ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

5 / 66


4. Pˇrehled tˇrídících algoritmu˚ Existuje velmi mnoho tˇrídících algoritmu. ˚ V praxi se používá pouze malé procento z nich, ostatní pˇredstavují spíše akademický problém. Vybrané elementární tˇrídící algoritmy (v praxi nepoužívané): ˇ pˇrímým vkládáním (Insert Sort) Tˇrídení ˇ binárním vkládáním (Insert Binary Sort) Tˇrídení ˇ (Bubble Sort) Bublinkové tˇrídení ˇ pˇrímým výberem ˇ Tˇrídení (Select Sort) ˇ se zmenšujícím se krokem (Shell Sort) Tˇrídení Vybrané profesionální tˇrídící algoritmy: Quick Sort ˇ sluˇcováním (Merge Sort) Tˇrídení ˇ haldou (Heap Sort) Tˇrídení ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

6 / 66


ˇ pˇrímým vkládáním: 5. Tˇrídení Insert Sort. ˇ Vhodný pro cˇ ásteˇcneˇ setˇrídené posloupnosti. Rychlejší než ostatní algoritmy s kvadratickou složitostí (Bubble Sort, Select Sort). Složitost O(N 2 ), poˇcet pˇresunu˚ Cmax = 0.5(n2 + n − 2), Cmin = 0.25(n2 + 9n − 10). ˇ Inspirován chováním hráˇce karet pˇri jejich tˇrídení. Hráˇc si vezme z balíˇcku karty a na základeˇ jejich velikosti a barvy je zaˇrazuje mezi ostatní karty. ˇ ˇ a karty Karty má rozdeleny na dveˇ podmnožiny: karty k setˇrídení ˇ již setˇrídené. ˇ Z nesetˇrídené podmnožiny vezme první kartu a vloží ji na správné ˇ ˇ místo v setˇrídené podmnožine. ˇ ˇ Postup opakuje, dokud má k dispozici nejakou nesetˇrídenou kartu. Základem dalších algoritmu: ˚ Insert Binary Sort cˇ i Shell Sort. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.) 7 / 66


ˇ pˇrímým vkládáním: 6. Princip tˇrídení ˇ Dveˇ podmnožiny: podmnožina setˇrídených prvku˚ S a podmnožina ˇ nesetˇrídených prvku˚ N. Start: dim(S) = 0, dim(N) = n. ˇ Prvek x0 v nesetˇrídené podmnožineˇ ponecháme na stejné pozici Prvek x1 porovnáme s prvkem x0 . Je -li x1 > x0 , ponecháme prvky ˇ beze zmeny. V opaˇcném pˇrípadeˇ zaˇradíme x1 na první pozici a odsuneme x0 o jednu pozici vpravo. Prvek x2 porovnáme s prvky x0 , x1 . Zaˇradíme prvek na správnou ˇ než x2 odsuneme smerem ˇ pozici, prvek/prvky vetší doprava. ˇ Postup opakujeme, dokud nesetˇrídená cˇ ást obsahuje alesponˇ jeden prvek. End: dim(S) = n, dim(N) = 0. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

8 / 66


6. Porovnávání prvku˚ ˇ Již setˇrídená posloupnost tvoˇrena prvky {x0 , ..., xi−1 }, Vkládaný prvek oznaˇcen jako xi . ˇ Zatím nesetˇrídená posloupnost tvoˇrena prvky {xi , ..., xn−1 }. ˇ Prvek xi−1 pˇredstavuje zarážku delící posloupnost na dveˇ podmnožiny. Princip porovnávání: ˇ Prvek xi porovnáme s posledním setˇrídeným prvkem xi−1 . Pokud xi ≥ xi−1 , prvek xi je na správné pozici. Inkrementujeme i = i + 1, opakujeme postup s následující dvojicí prvku. ˚ Pokud xi < xi−1 , prohodíme prvky xi a xi−1 . Prohozený prvek xi−1 porovnáme s pˇredchozím prvkem xi−2 . ˇ Pokud není splnena podmínka xi−1 ≥ xi−2 , prohodíme prvky xi−1 a xi−2 Pokraˇcujeme analogickým zpusobem, ˚ dokud vkládaný prvek není na správné pozici ⇒ konec. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

9 / 66


ˇ algoritmu Insert Sort 7. Znázornení


10 / 66


8. Zdrojový kód Insert Sort: Realizován dvojicí cyklu. ˚ ˇ probíhá nad všemi prvky. Vnejší ˇ Vnitˇrní, dokud není prvek na správném míste.

void insertSort(double x []) { for(int i = 0;i < x.length; i++) { int j = i; //Zapamatuj index zpracovávaného prvku double prvek = x[i]; while (j > 0 && x[j-1] > prvek) //Porovnavani s seteridenou cas { temp = x[j]; //Prohozeni za pouziti x[j] = x[j-1]; //pomocne promenne temp x[j-1] = temp; j = j - 1; //Dekrementace indexu } } } ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

11 / 66


9. Modifikace algoritmu pˇrímého vkládání Nepoužíváme zarážku, v každém porovnávání neprohazujeme testovaný prvek s prvkem pˇredchozím. ˇ než tento prvek Prvky pole nacházející se vlevo od testovaného prvku vetší posunujeme v každém kroku o 1 pozici vpravo. Do vzniklé mezery zapíšeme testovaný prvek.

void insertSort(double x []) { for(int i = 0;i < x.length; i++) { int j = i; double prvek = x[i]; while (j > 0 && x[j-1] > prvek) { x[j] = x[j-1]; //Posun prvku o 1 pozici vpravo j = j - 1; //Dekrementace indexu } x[j] = prvek; //Zarazeni prvku na spravne misto } ˇ Tomáš Bayer}| [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.) 12 / 66


ˇ binárním vkládáním 10. Tˇrídení =Insert Binary Sort. ˇ vkládáním, snaha urychlit nalezení místa, kam prvek patˇrí. Vylepšené tˇrídení Pro urychlení používáme binární vyhledávání (O(log2 N) vs. O(N) ). Princip algoritmu: ˇ Binární vyhledávání probíhá v setˇrídené cˇ ásti pole v intervalu < 0, i − 1 >. V indexu l Binary Search bude uložena správná pozice prvku x[i]. Následneˇ odsuneme všechny prvky v intervalu < l, i − 1 > o jednu pozici vpravo. Na pozici l pˇresuneme kopírovaný prvek. Výrazné navýšení rychlosti algoritmu.


13 / 66


11. Zdrojový kód binárního vkládání void insertBinarySort(double x[]) { for (int i = 0; i < x.length; i++) { int j = i; double prvek = x[i]; int l = 0, p = i - 1; //Levy a pravy index while (l <= p) { //Binary Search int k = (l + p) / 2; if (prvek > x[k]) l = k + 1; else p = k - 1; } while (j > l) { //Index l = hledana pozice x[j] = x[j - 1]; //Posun prvku o 1 pozici vpravo j = j - 1; //Dekrementace indexu } x[l] = prvek; //Zarazeni prvku na spravne misto } }


14 / 66


ˇ 12. Bublinkové tˇrídení Bubble Sort. Nejpomalejší ze všech uvedených. ˇ ˇ naprázdno (možné odstranit). Nevhodné pro cˇ ásteˇcneˇ setˇrídené posloupnosti, beží Složitost O(N 2 ), poˇcet pˇresunu˚ Cmax = 0.75(n2 − n).

Popis algoritmu: ˇ které postupneˇ stoupají Odvozen od chování vzduchových bublinek limonáde, ˇ vzhuru ˚ k hladine. Porovnávány dva sousední prvky xi a xi−1 . Pokud xi < xi−1 , prohodíme oba prvky. V opaˇcném pˇrípadeˇ je ponecháme ve stejném poˇradí a porovnáme následující dvojici prvku. ˚ Porovnávání zaˇcíná od konce pole. Prvky s menší hodnotou se postupneˇ ˇ pˇresouvají zprava doleva jako bublinky v limonáde. Po prvním pruchodu ˚ prvek x0 pˇredstavuje minimum, v dalším kroku již nemusíme procházet celé pole, ukonˇcíme ho na prvku x1 . ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

15 / 66


ˇ algoritmu 13. Znázornení


16 / 66


14. Zdrojový kód Realizován dvojicí cyklu. ˚ ˇ probíhá nad všemi prvky. Vnejší ˇ Vnitˇrní o 1x méne. void bubbleSort(double x []) { for (int i = 0;i < x.length; i++) { for (int j = x.length-1; j > i; j--) //Prohledavani od konce

{ if (x[j] < { double x[j] = x[j-1] }

x[j-1]) temp = x[j]; x[j-1]; = temp;

//Prohozeni za pouziti //pomocne promenne temp

} } } ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

17 / 66


15. Zhodnocení algoritmu Nesymetrická rychlost bublání prvku: ˚ Prvky malých hodnot stoupají rychleji než prvky velkých hodnot klesají. Po prvním vykonání vnitˇrního cyklu se minimální hodnota nachází na první pozici, zatímco nejvyšší hodnota se posune pouze o jednu pozici. ˇ bubláním: Nevýhoda tˇrídení Znaˇcná závislost na vstupních datech. ˇ ˇ Pokud jsou vstupní data ve tvaru, kdy je vetšina prvku˚ již setˇrídena, ˇ v nekterých ˇ algoritmus beží krocích “naprázdno”, neprovádí žádné prohazování. ˇ ˇ Pokud bychom na vstup dali již setˇrídená data, probehnou oba cykly vˇcetneˇ testovací podmínky. ˇ Casová složitost: ˇ ˇ bubláním je O(N 2 ). Nelze použít pro rozsáhlá Casová složitost tˇrídení data.


18 / 66


ˇ 16. Modifikace bublinkového tˇrídení ˇ prázdných kroku. Odstranení ˚ ˇ Pomocná promenná typu boolean sort, pokud je true, posloupnost je ˇ setˇrídena. void bubbleSort(double x []) { bool sort = false; for (int i = 0; !sort; i++) { sort = true; for (int j = x.length - 1; j > i; j--) { if (x[j] < x[j-1]) { double temp = x[j]; x[j] = x[j-1]; x[j-1] = temp; sort = false; } } } }

//Setridena posloupnost //Prohledavani od konce

//Prohozeni za pouziti //pomocne promenne tep //Neni setridena posloupnost


19 / 66


ˇ pˇrímým výberem: ˇ 17. Tˇrídení Select Sort. ˇ než Insert Sort. Efektivnejší ˇ krátkých posloupností u algoritmu QuickSort. Používá se na dotˇrídení 2 Složitost O(N ), poˇcet pˇresunu˚ Cmax = 0.25N 2 + 3(N − 1). Popis algoritmu: ˇ využívaly porovnání aktuálního prvku xi s Pˇredchozí techniky tˇrídení ostatními prvky posloupnosti, na základeˇ výsledku této relace s ˇ další operace. prvkem xi provádely ˇ nevybírá prvky z nesetˇrídené ˇ Tato metoda tˇrídení cˇ ásti posloupnosti ˇ ale na základeˇ jejich hodnoty. sekvenˇcne, ˇ Prvek je vložen do setˇrídené cˇ ásti na pˇredem známou pozici, která se ˇ ˇ nemení, ˇ již v prub ˚ ehu tˇrídení v pˇredchozích algoritmech se jeho ˇ hodnota menila (odsouvání cˇ i prohazování). Nelze použít pro rozsáhlejší data.


20 / 66


18. Princip algoritmu ˇ ˇ Tˇrídená posloupnost je rozdelena na dveˇ cˇ ásti: levá obsahuje již ˇ setˇrídené prvky posloupnosti ve správném poˇradí, pravá prvky dosud ˇ nesetˇrídené. Start: dim(S) = 0, dim(N) = n. 1

2

3

4 5

V prvním kroku nalezneme hodnotu xmin = min(xi ), i = 1, .., N, tj. prohledáváme celou posloupnost prvku. ˚ Hodnotu xmin prohodíme s hodnotou x0 . Prvek x0 se nachází na ˇ ˇ nebude menit. ˇ správné pozici, jeho poloha se již v prub ˚ ehu tˇrídení ˇ V druhém kroku hledáme minimum z nesetˇrídené cˇ ásti prvku, ˚ tj. xmin = min(xi ), i = 2, .., N. Tento prvek prohodíme s prvkem x1 . ˇ nebude menit. ˇ Poloha prvku x1 se již pˇri dalším tˇrídení Opakujeme. ˇ prvek xn bude umísten ˇ na správném míste. ˇ Poslední nesetˇrídený

End: dim(S) = n, dim(N) = 0. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

21 / 66


19. Ukázka algoritmu


22 / 66


20. Zdrojový kód ˇ realizováno dvojicí cyklu. Tˇrídení ˚ void selectSort(double x []) { for (int i = 0; i < x.length - 1; i++) { double min = x[i]; //Inicializace minima int index = i; //Inicializace indexu for (int j = i; j < x.length; j++) //Hledani minima { if (min > x[j]) { min = x[j]; index = j; } } double temp = x[i]; //Prohozeni promennych x[i] = min; x[index] = temp; } } ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.) 23 / 66


21. Modifikace algoritmu Ve vnitˇrním cyklu nebudeme hledat minimum, ale pouze index minima. void selectSort(double x []) { for (int i = 0; i < x.length; i++) { int index = i ; for (int j = i; j < x.length; j++) { if (x[index]> x[j]) index = j; } double temp = x[i]; x[i] = x[index]; x[index] = temp; } }

//Inicializace indexu //Hledani indexu minima

//Prohozeni promennych

ˇ Modˇre znázorneno hledání indexu minima. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

24 / 66


ˇ se zmenšujícím se krokem 22. Tˇrídení =Shell Sort. Eliminuje neefektivitu pˇredchozích algoritmu˚ spoˇcívající v prohazování na krátké vzdálenosti. Neprohazuje pouze sousední prvky, provádí prohazování prvku˚ s krokem h. ˇ Takový soubor nazýván h−setˇrídený. ˇ Krok h se neustále zmenšuje, pro h = 1 je soubor setˇríden. Možnosti volby kroku h: hi

=

3hi−1 + 1,

hi

=

2hi−1 + 1.

Posloupnosti se stˇrídajícími se lichými a sudými cˇ leny: h

=

{1, 4, 13, 40, 121, 364, 1093, 3280, 9841, ...}

h

=

{1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, ...}

ˇ Pro malé kroky h už zbývá málo prohozu, ˚ vetšina vykonána v pˇredcházejících krocích ˇ s vetším h. ˇ ze všech elementárních Výhodou snížení složitosti až na O(N 1.2 ), nejpˇríznivejší algoritm u. ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.) 25 / 66


23. Princip algoritmu ˇ ˇ Algoritmus je zobecnením Insert Sortu (nejˇcastejší). Pro prohazování však existují i jiné metody (napˇr. bublání). ˇ Shell Sort pro h = 1 Insert Sortem nad již cˇ ásteˇcneˇ setˇrídenou posloupností. Postup: Výpoˇcet iniciaˇcní hodnoty kroku h = 3h + 1, h < n. Opakuj pro h = h/3 Insert Sort s krokem h. Neporovnáváme sousední prvky x[j] a x[j − 1], ale x[j] a x[j − h]. Dusledky: ˚ ˇ Ve vnejším cyklu Insert Sort nahradíme inicializaci i=0 za i = h Ve vnitˇrním cyklu Insert Sortu nahradíme všechny výskyty indexu j − 1 za j − h. ˇ Jednoduchá implementace, pouze malá zmena algoritmu Insert Sort pˇrinese znaˇcné zvýšení výkonu. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

26 / 66




27 / 66




28 / 66


26. Zdrojový kód public void int for for

shellSort(double x[]) { h; (h = 1; h < x.length - 1; h = 3 * h + 1); //Nastaveni h (h /= 3; h > 0; h /= 3) { for (int i = h; i < x.length; i++) { //Inkrementace i o int j = i ; double prvek = x[i]; while ((j >= h) && (x[j - h] > prvek)) { x[j] = x[j - h]; //Posun prvku o h pozic j = j - h; //Dekrementace indexu o } x[j] = prvek; //Zarazeni prvku na spra }

} } ˇ Insert Sort. Modˇre znázornen Pozor: netestujeme prvky x[j] a x[j-1] ale x[j] a x[j-h]! ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

29 / 66

QuickSort

28. QuickSort ˇ Jeden z nejpoužívanejších tˇrídících algoritmu. ˚ ˇ a panuj, lze implementovat rekurzivneˇ i Využívá principu rozdel ˇ nerekurzivne. Vysokého výkonu dosáhne prohazování prvku˚ na velké vzdálenosti. Inspirace: ˇ ∀i ∈ h1, ni platí xi ≥ xi+1 . Posloupnost prvku˚ seˇrazených sestupne: ˇ takovou posloupnost setˇrídit vzestupne, ˇ jako Pokud bychom chteli velmi rychlý by se jevil následující postup prohazování: x1 ⇔ xn , ˇ x2 ⇔ xn−1 ,..., tj. výmena prvního prvek s posledním, druhého s pˇredposledním, atd. ˇ n − 1 výmen, ˇ ale pouze V takovém pˇrípadeˇ nebude potˇreba k setˇrídení n/2. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

30 / 66

QuickSort

29. Princip QuickSortu V prvním kroku je zvolena stˇrední hodnota x, tzv. pivot. ˇ Posloupnost je uspoˇrádána rozdelením na dveˇ cˇ ásti tak, že levá cˇ ást obsahuje prvky xi < x, pravá cˇ ást prvky xi > x.

ˇ pˇredstavovat Hodnota pivotu x muže ˚ být zvolena náhodne, ˇ (viz dále). medián cˇ i aritmetický prum ˚ er ˇ ˇ Každá z techto cˇ ástí je stejným zpusobem ˚ rekurzivneˇ rozdelena. ˇ Poˇcty úseku˚ se s každým delením zdvojnásobují, délky úseku˚ (tj. poˇcty prvku) ˚ snižují na polovinu. ˇ Delení provádíme tak dlouho, dokud délky úseku˚ nejsou rovny ˇ jedné. V takovém pˇrípadeˇ je posloupnost setˇrídena. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

31 / 66

QuickSort

30. Volba pivota B) první prvek x = x1 Pivot je pˇredstavován prvním prvkem z posloupnosti. ˇ O(N 2 ). Jedná se o nejméneˇ výhodnou volbu, složitost tˇrídení Degenerovaný strom, výška N − 1. B) medián x = xb Nejlepší varianta, strom s výškou log2 (N). Ale složitost nalezení mediánu je O(N). Složitost celkem O(N 2 ). C) náhodný prvek x = rand(xi ) ˇ používaná varianta, složitost algoritmu je (N log N), ale O(N 2 )! Nejˇcasteji ˇ ˇ r tak rychlý, jako pˇri použití mediánu. Algoritmus je ve vetšin eˇ pˇrípadu˚ témeˇ ˇ Pravdepodobnost, že pˇri každém náhodném volání nalezen první prvek, malá. ˇ Nevýhodou algoritmu QuickSort je jeho promenná cˇ asová složitost závisející ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

32 / 66

QuickSort

31. QuickSort Pseudokód algoritmu QuickSort QuickSort(double [] pole, int levy, int pravy) { int m = (int)(0.5 * (l + p)); //Prostredni prvek /* Vlastni trideni */ QuickSort(pole, levy, m-1); QuickSort(pole, m+1, pravy);

//Setrideni leve poloviny //Setrideni prave poloviny

} QuickSort lze realizovat s použitím rekurze cˇ i pˇrevodem na zásobník. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

33 / 66

QuickSort

32. Prohazování prvku˚ v QuickSortu

ˇ prvky: Snaha prohazovat co nejvzdálenejší ˇ Od prvku x1 postupujeme smerem vpravo a hledáme prvek, pro který platí xv > x. ˇ Od prvku xn postupujeme smerem vlevo a hledáme prvek, pro který platí xm < x. Oba prvky prohodíme. ˇ prohledávání setkají, v takovém pˇrípadeˇ Uprostˇred pole se smery je postup ukonˇcen.


34 / 66

QuickSort

ˇ algoritmu QuickSort 25. Znázornení


35 / 66

QuickSort

33. Zdrojový kód prohazování prvku˚ ˇ cyklus probíhá, dokud je prvky vlevo od pivotu vetší ˇ než vpravo Vnejší od pivotu. while(i < j) { while (x[i] < piv) i = i + 1; while (piv < x[j]) j = j - 1; if (i <= j) { double pom = x[i]; x[i] = x[j]; x[j] = pom; i = i + 1; j = j - 1; } }

//Hledani prvku zleva, ktery se vymeni //Hledani prvku zprava, ktery se vymeni //Prohozeni obou prvku

//Posun leveho indexu vpravo //Posun praveho indexu vlevo

Urˇcení pivota: piv = [int((l + p)/2)] ve snaze se co nejvíce pˇriblížit mediánu. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

36 / 66

QuickSort

34. Zdrojový kód QuickSortu

void QuickSort(double x [], int l, int p) { int i = l; int j = p; double piv = x[int((l + p) / 2)]; //Urceni pivota while(i < j) { while (x[i] < piv) i = i + 1; //Hledani prvku zleva, ktery se vymeni while (piv < x[j]) j = j - 1; //Hledani prvku zprava, ktery se vymen if (i <= j) //Prohozeni obou prvku { pom = x[i]; x[i] = x[j]; x[j] = pom; i = i + 1; //Posun leveho indexu vpravo j = j - 1; //Posun praveho indexu vlevo } } if (l < j) QuickSort(x,l,j); //Rekurze if (i < p) QuickSort(x,i,p); //Rekurze }


37 / 66

QuickSort

35. Zhodnocení algoritmu QuickSort ˇ velkých polí. Algoritmus QuickSort je velmi efektivní pro tˇrídení Nejrychlejší tˇrídící algoritmus. Jeho efektivita velmi výrazneˇ závislá na volbeˇ pivota, nejrychlejší levá a pravá cˇ ást stejneˇ velké. Z tohoto duvodu ˚ není používán v cˇ asoveˇ kritických aplikacích. ˇ malých polí (cca do 12 prvku) Pro tˇrídení ˚ je pˇrekvapiveˇ málo efektivní, dosahuje horších výsledku˚ než Insert Sort. V praxi je QuickSort ukonˇcován, pokud je délka posloupnosti získaná ˇ rekurzivním delením kratší než 12 prvku. ˚ ˇ Posloupnost následneˇ dotˇrídena jiným zpusobem, ˚ napˇr. Select Sort.


38 / 66


ˇ 36. Tˇrídené sléváním = Merge Sort ˇ a panuj, rekurzivní algoritmus (rozdel ˇ = rekurze, Založen na principu Rozdel spoj = merge). ˇ Využívá princip zatˇrid’ování ⇒ slouˇcení dvou menších setˇrídených souboru˚ ˇ ˇ do jednoho vetšího setˇrídeného souboru. Složitost algoritmu (na rozdíl od QuickSortu) vždy, není závislá na pivotovi. ˇ Ve vetšin eˇ pˇrípadu˚ je MergeSort pomalejší než QuickSort, není však citlivý vuˇ ˚ ci vstupním datum, ˚ stabilní. ˇ Používán jako standardní tˇrídící algoritmus v Jave. Princip algoritmu: ˇ Rozdelení posloupnosti s n prvky na dveˇ podposloupnosti s n2 prvky. ˇ Delení rekurzivneˇ opakováno, dokud podposloupnosti nejsou tvoˇreny jedním ˇ prvkem (takové jsou považovány za setˇrídené). Opakované spojování dvou podposloupností v jednu seˇrazenou ˇ podposloupnost, dokud nevznikne setˇrídená posloupnost s n prvky. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

39 / 66


ˇ sléváním 37. Vlastní algoritmus tˇrídení ˇ Pole je rozdeleno na dveˇ cˇ ásti. ˇ Na každou cˇ ást rekurzivneˇ voláno setˇrídení. ˇ (spojeny). Obeˇ poloviny následneˇ zatˇrídeny void MergeSort (double [] a, int l, int p) { int m = (l + p) / 2;

//Prostredni prvek

if (p <= l) return; MergeSort(a, l, m); MergeSort(a, l+1, p); merge (a, l, m, p);

//Prazdny interval, spojeni //Setrid levou polovinu //Setrid pravou polovinu //Spoj poloviny zatridenim

} ˇ na pole pˇri zatˇrid’ování. Nevýhodou dodateˇcná pamet’ ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

40 / 66


ˇ algoritmu 38. Znázornení

6 3 1 1 1 1 1 1 1

3 6 3 3 3 3 3 3 3

1 1 6 6 5 5 5 5 5

5 5 5 5 6 6 6 6 6

15 15 15 15 15 15 15 15 15

4 4 4 4 4 4 4 4 0

8 8 8 8 8 8 7 7 4

7 7 7 7 7 7 8 8 7

9 9 9 9 9 9 9 0 8


0 0 0 0 0 0 0 9 9

41 / 66


39. Druhy zatˇrid’ování Dvoucestné zatˇrid’ování: Pole a tvoˇreno n prvky, pole b tvoˇreno m prvky, sluˇcované pole c tvoˇreno n + m prvky. Pˇri každém pruchodu ˚ cyklem nalezneme minimální hodnotu z obou polí a, b a pˇridáme ji do sluˇcovaného pole c. ˇ Nutno vytvoˇrit dveˇ pomocná pole, dodateˇcné pamet’ové nároky. Režie spojená s kopírováním vstupního pole do obou pomocných polí. V praxi se nepoužívá. ˇ Zatˇrid’ování na míste: Pouze jedno pomocné pole, rychlejší. Levá polovina pomocného pole obsahuje kopii levé poloviny vstupního pole. Pravá polovina pomocného pole obsahuje kopii pravé poloviny vstupního pole v opaˇcném poˇradí. ˇ Tomáš Bayer rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.) 42 / 66 ˇ | [email protected] (Katedra aplikovanéTˇgeoinformatiky ˇ


40. Dvoucestné zatˇrid’ování void merge(double [] c, double [] a, double [] b){ int N = a.length; int M = b.length; for (int i = 0, int j = 0, int k = 0; k < N + M; k++) { if (i == N) { //Pole a uz nema dalsi prvky c[k] = b[j]; j++; continue; //Skok na dalsi iteraci } if (j == M) { //Pole b uz nema dalsi prvky c[k] = a[i]; i++; continue; //Skok na dalsi iteraci } if (a[i] < b[j]) { c[k] = a[i]; //Pridani mensiho prvku i++; } else { c[k] = b[j]; //Pridani mensiho prvku j++; } } } ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

43 / 66


41. Upravené dvoucestné zatˇrid’ování public void merge(double[] c, int l, int mid, int p) { int n = mid - l + 1; int m = p - mid; double[] a = new double[n]; //Pomocne pole a double[] b = new double[m]; //Pomocne pole b System.arraycopy(c, l, a, System.arraycopy(c, mid + int i = 0, j = 0, k = 0; for (; k < n + m; k++) { if (i == n) { c[k+l] = b[j]; j++; continue; } if (j == m) { c[k+l] = a[i]; i++; continue;

0, n); //Zkopiruj obsah pole c 1, b, 0, m); //Zkopiruj obsah pole c

//Pole a uz nema dalsi prvky

//Skok na dalsi iteraci //Pole b uz nema dalsi prvky

//Skok na dalsi iteraci


44 / 66


42. Zatˇrid’ování na místeˇ void merge (double [] a, int l, int m, int p) { double temp[n]; //Pomocne pole int i, j, k; for (i = m + 1; i > 1; i--) { temp[i-1] = a[i -1]; //Kopie prvniho pole } // i = 1 for (j = m; j < p; j++) temp[p + m - j] = a[j+1]; //Kopie druheho pole v opacnem poradi } //j = r for (k = 1; k <= p; k++) { if (a[i] < a[j]) { //Nalezeni mensiho prvku a[k] = temp[i]; //Pridani do pole i++; } else { a[k] = temp[j]; //Pridani do pole j--; } } }


45 / 66


43. Halda Halda (heap): datová struktura pˇredstavovaná binárním stromem. Proˇc Heap Sort použita halda s globálním minimem v koˇrenu. Definice: Halda pˇredstavuje takovou posloupnost prvku˚ hl , hl+1 , hl+2 , ..., hr , že pro každý index i = l, ..., r /2 platí hi ≤ h2i

\

hi ≤ h2i+1 .

Pˇríklad: Halda definována posloupností h1 , h2 , ..., hn , kde i = n/2. Koˇren stromu h1 , h2 levý potomek, h3 pravý potomek. Levý potomek uzlu h2 je h4 , pravý potomek je h5 , atd. Všichni leví potomci mají sudý index, všichni praví potomci levý index. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

46 / 66


44. Ukázka haldy

h1

h3

h2

h5

h4

h8

h9

h10

h6

h11

h12

h7

h13

h14

h15


47 / 66


45. Ukázka haldy

6

10

33

15

25

19

22

31

38

30

45

65

54

85

93


48 / 66


46. Halda a její reprezentace Dusledky ˚ plynoucí z definice: Binární strom je haldou práveˇ když hodnota uzlu je menší nebo rovna hodnoteˇ potomku. ˚ Žádný uzel nemá menší hodnotu než koˇren. Haldu lze reprezentovat polem, výhodou rychlý pˇrístup. []

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

x

6

10

33

15

19

38

65

25

22

31

30

45

54

85

93

Vztahy mezi poˇradovým cˇ íslem uzlui ve stromu a indexy pole[i]: Rodiˇc: [i/2]. Levý potomek: [2i]. Pravý potomek: [2i + 1]. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

49 / 66


47. Operace nad heapem

ˇ posloupnosti: Operace nad heapem nutné k setˇrídení pˇridání prvku do heapu, oprava heapu nahoru: fixHeapUp, oprava heapu dolu: ˚ fixHeapDown, tisk heapu.


50 / 66


47. Oprava haldy nahoru ˇ Pohyb haldou od uzlu U smerem ke koˇreni haldy, nemá vliv na potomky U. Stromová reprezentace: Pokud pˇredchudce ˚ P uzlu U má vyšší hodnotu, prohodíme U ⇔ P. Pokraˇcujeme v pˇredchudci ˚ U = P, dokud U není koˇren. Reprezentace polem: Pokud prvek [i/2] má menší hodnotu než prvek [i], prohodíme [i/2] ⇔ [i]. Pokraˇcujeme v pˇredchudci ˚ i = i/2 dokud i > 1. public void fixHeapUp(double[] h, int i) { while (i > 1 && (h[i / 2] > h[i])) { //Opakuj pro predchudce double temp = h[i / 2]; //Prohozeni s pouzitim h[i / 2] = h[i]; //lokalni promenne h[i] = temp; i = i / 2; //Jdi na rodice } } ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

51 / 66


48. Ukázka opravy haldy nahoru

6

19

33

15

25

30

22

31

38

10

45

65

54

85

93


52 / 66


49. Ukázka opravy haldy nahoru (30<->10)

6

19

33

15

25

10

22

31

38

30

45

65

54

85

93


53 / 66


50. Ukázka opravy haldy nahoru (10<->19)

6

10

33

15

25

19

22

31

38

30

45

65

54

85

93


54 / 66


51. Oprava haldy dolu˚ ˇ Pohyb haldou od uzlu U smerem od koˇrene k listum ˚ haldy, nemá vliv na pˇredchudce ˚ U. Stromová reprezentace: Najdi následníky uzlu U: VL , VP . Pokud VP < VL , následník V = VP , jinak V = VL (pˇridáváme do menšího). Pokud U > V , prohod’ U ⇔ V , jinak ukonˇci. Pokraˇcuj v prohozeném vrcholu, dokud nedosáhneme listu. Reprezentace polem: Najdi následníky uzlu [i]: [2 ∗ i], [2 ∗ i + 1]. Pokud [2 ∗ i + 1] < [2 ∗ i] , následník [v ] = [2 ∗ i + 1], jinak [v ] = [2 ∗ i] (pˇridáváme do menšího). Pokud [i] > [v ], prohod’ [i] ⇔ [v ] jinak ukonˇci. Pokraˇcuj v prohozeném vrcholu, dokud nedosáhneme listu


55 / 66


52. Algoritmus pro opravu haldy dolu˚ public void fixHeapDown(double[] h, int k, int n) { int i; while (2 * k <= n) { i = 2 * k; //Levy potomek if (i < n && h[i + 1] < h[i]) //Porovnani L a P potomka { i++; //Index ukazuje na mensiho potomka } if (h[k] > h[i]) //Nesplneny podminky, prohodit { double temp = h[k]; h[k] = h[i]; h[i] = temp; } else { break; //Ukonceny podminky, nepokracuj } k = i; //Pokracuj od prohozeneho potomka } } ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

56 / 66


53. Ukázka opravy haldy dolu˚

6

19

33

15

18

30

22

31

38

32

45

65

54

85

93


57 / 66


54. Ukázka opravy haldy dolu˚ (19<->15)

6

15

33

19

18

30

22

31

38

32

45

65

54

85

93


58 / 66


55. Ukázka opravy haldy dolu˚ (18<->19)

6

15

33

18

19

30

22

31

38

32

45

65

54

85

93


59 / 66


56. Pˇridání prvku a do haldy Opakuj, pro ∀xi ∈ x: ˇ Nový uzel U s hodnotou xi vytvoˇren na poslední hladine. Propojení uzlu U s uzlem P ležícím na pˇredposlední hladineˇ co nejvíce vlevo. Oprava haldy nahoru U. ˇ Heap pˇredstavován polem h s délkou n+1, tj. o jednu pozici delší než poˇcet tˇrídených prvku˚ v x (pˇridáváme od 1). ˇ po ˇrádcích, po každém vložení inkrementován index i o 1. Heap plnen int i = 1; for (int k = 0; k <= x.length - 1; k++) { h[i] = x[k]; //Pridej do heapu fixHeapUp(h, i); //Oprav heap nahoru do akt. pozice i++; //Inkrement i }


60 / 66


57. Ukázka budování haldy 3 3

1 3

1 1

5

3

5

3

1 6

6

2

1 5

3

5

3 6

1 2

1

1 5

2 6

3

9

5

2 6

3

9

4


61 / 66


58. Vlastní tˇrídící algoritmus ˇ eˇ triviální. Probíhá nad vybudovanou haldou pomern Opakuj, dokud halda neobsahuje pouze koˇren: Prohození koˇrene (minima haldy) s prvkem haldy nejnižší úrovneˇ nejvíce vpravo. Oprava haldy dolu˚ (v koˇreni není minimum). Zkrácení haldy o prvek nejnižší úrovneˇ nejvíce vpravo. Nad polem snadno algoritmizovatelné. Opakuj, dokud n > 1 Prohodíme h[1] a h[n]. Provedeme opravu haldy dolu˚ z koˇrene. Dekrementujeme n. ˇ nejmenší prvek, druhý výber: ˇ druhý nejmenší prvek, atd. První výber: ˇ Jsou ˇrazeny za koncem zkracované haldy sestupne. ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

62 / 66


59. Ukázka cˇ innosti algoritmu 5

1 2 6

4 3

2 5

9

6

3

2

5

6

1

6

9

2

2

1

4

1

6

9 3

1

4 3

2

1

5

5

9

9

5

4

6

5 3

1

9

5

4

4

; 6

9

4

3

3 5

3

4

9

6

2

2

6 1

4

9 3

2


1 63 / 66


59. Algoritmus Heap Sort Pouze tˇrídící procedura: while (n > 1) { double temp = h[1]; //Vem nejmensi prvek h[1] = h[n]; //Prohod s poslednim h[n] = temp; n--; //Zkrat heap o 1 fixHeapDown(h, 1, n); } Vlastnosti algoritmu: Algoritmus má složitost O(N lg2 N). Asi o 20% pomalejší než Merge Sort a o 50% pomalejší než Quick Sort. ´ Použití pro hledání k − t eho nejmenšího prvku. Nevýhodou nestabilita.


64 / 66


60. Zdrojový kód (celek) public void heapSort(double[] x) { int i = 1, n = x.length; double[] h = new double[n + 1]; //Heap o jeden prvek delsi for (int k = 0; k < n; k++) //Pridej vsechny prvky,oprav heap { h[i] = x[k]; //Pridej do heapu fixHeapUp(h, i); //Oprav heap zdola i++; //Inkrementuj i } while (n > 1) { double temp = h[1]; //Vem nejmensi prvek h[1] = h[n]; //Prohod s poslednim h[n] = temp; n--; //Zkrat heap fixHeapDown(h, 1, n); } } ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

65 / 66

Pˇrehled tˇrídících algoritmu˚

34. Pˇrehled tˇrídících algoritmu˚

Selection Sort Bubble Sort Insertion Sort Merge Sort Quick Sort Heap Sort

Worst case

Average case

n2

n2 n2 n2 n lg n n lg n n lg n

n2 n2 n lg n n2 n lg n

Další odkazy: http://en.wikipedia.org/wiki/Sorting_algorithm http://coderaptors.com/?All_sorting_algorithms http://www.ida.liu.se/~TDDB28/mtrl/demo/sorting/index.sv.shtml http://math.hws.edu/TMCM/java/xSortLab/ ˇ Tomáš Bayer | [email protected] (Katedra aplikovanéTˇ geoinformatiky rídící algoritmy.a kartografie, Pˇrírodovedecká fakulta UK.)

66 / 66

Třídící algoritmy. Insert Sort. Bubble Sort. Select Sort. Shell Sort. Quick Sort. Merge Sort. Heap Sort

Recommend Documents