Basic Information

A survey on sorting algorithms and their analysis. Sequential and parallel sorting algorithms, internal and external sorting.

Time and Location	Mon 15:40 - 17:10 in S301
Winter Term	2/0 Zk
Information in SIS:	NTIN058

Syllabus

Interní třídění

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)

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

Externí třídění

Míry složistosti externích algoritmů a odhad složitosti externího třídění obecně

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

Třídění na discích

externí Bubblesort, Mergesort, Quicksort (Exquisit) a Heapsort

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í

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ů

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

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ů

Sorting