Třídění

Aktuální obsah přednášky

1. Interní třídění

1.1. Algoritmy založené na porovnávání prvků
Dolní odhad složitosti obecně - rozhodovací stromy
Přímé metody:
třídění vkládáním - Insertionsort (složitost v nejhorším případě a očekávaná složitost, Binární Insertionsort)
třídění výběrem - Selectionsort (složitost v nejhorším a průměrném případě, modifikace algoritmu vedoucí k lepší složitosti)
třídění výmenou - Bubblesort (složitost, adaptace na předtříděné posloupnosti, Shakersort)
Vylepšení přímých metod:
Shellsort (Shellova, Hibbardova a Prattova varianta - výpočet složitosti v nejhorším případě, Sedgewickova varianta, rovnoměrné a nerovnoměrné varianty, problémy s očekávanou složitostí, experimentální výsledky)
Optimální algoritmy (alespoň v průměrném případě):
třídění haldou - Heapsort (definice binární haldy, haldové operace, způsoby budování haldy a jejich složitost, klasický Williamsův a Floydův Heapsort, Bottom-up Heapsort, Heapsort s rekurzí - odvození složitosti, okrajově: Heapsort na víceregulárních haldách, Weak-Heapsort, Quick-Heapsort)
třídění sléváním - Mergesort (přímý Mergesort, metoda Divide et impera - výpočet složitosti pomocí rekurentního vztahu, přirozený Mergesort, mergování posloupností nestejných délek - slučovací strom a binární mergování, mergování na místě)
třídění rozdělováním - Quicksort (deterministický Hoareův Quicksort - výpočet složitosti v nejhorším a průměrném případě, volba dělicího prvku - výpočet mediánu, randomizovaný Quicksort, dotřiďování zbytkových polí, Quicksort bez zásobníku)

1.2. Algoritmy, které nepoužívají porovnávání, a hybridní algoritmy
Časová a prostorová složitost obecně
přihrádkové třídění - Bucketsort a Radixsort, Bucketsort na místě
Hybridsort - výpočet složitosti v nejhorším a průměrném případě
okrajově: metoda Distributive partitioning, Linear Probing Sort

2. Externí třídění
Míry složistosti externích algoritmů a odhad složitosti externího třídění obecně
2.1 Třídění na páskách
přímý a přirozený Mergesort bez využití interní paměti, dvoufázové a jednofázové megrování (vyvážené)
Mergesort s využitím interní paměti: vytvoření běhů - metoda Replacement selection, vícecestné a vícefázové mergování (nevyvážené - optimální rozělení běhů na pásky)
přihrádkové třídění na páskách, Quicksort na dvou páskách
2.2 Třídění na discích
externí Bubblesort, Mergesort, Quicksort (Exquisit) a Heapsort

3. Paralelní třídění
Modely paraleních výpočtů - paralelní počítač a distribuovaný výpočetní systém, modely SIMD a MIMD, modely speciální a víceúčelové, paralení RAM s režimem EREW, CREW a CRCW, sítě s různými způsoby propojení procesorů
Míry složitosti paraleních algoritmů - počet procesorů, paralení čas, cena
Dolní odhad složitosti pro paralení třídění
3.1. Třídicí sítě
Batcherovy třídicí sítě na principu Mergesortu a bitonické třídění - konstrukce, důkaz korektnosti, odvození hloubky a počtu komparátorů
3.2. Víceúčelové sítě
Model SIMD s lineárně propojenými procesory: Odd-even Transposition Sort a Merge-splitting Sort - výpočet paraleního času a ceny
Mergesort na rouře - výpočet paralelního času a ceny
Model SIMD se stromovou strukturou: třídění extrakcí minima, Bucketsorting and Merging, Median-splitting Sort - výpočet paralelního času a ceny
3.3. Model SIMD se sdílenou pamětí - paralelní RAM
čtení ze sdílené paměti v režimu EREW - Broadcast, paralelní výpočet k-tého nejmenšího prvku - Parallelselect, paralelní varianta Quicksortu - Sharesort
výpočet paralelního času a ceny při omezeném počtu procesorů
3.4. Asynchronní třídění
algoritmus Ennumeration Sort