Kapitola 1
Státnice - Třídění

1.1 Třídění založené na porovnávání

Existuje mnoho algoritmů, známe i (za určitých podmínek) dolní odhad složitosti.

Heapsort

HEAPSORT je třídění pomocí (např.) -regulárních hald, jen lokální podmínku haldy používáme v duální podobě a máme funkci DELETEMAX (která ale funguje stejně jako DELETEMIN). Postupně se odebírají maxima a setříděná posloupnost se staví na jejich místě od konce pole. Iterace končí, když v haldě zbývá jen jeden prvek. Celkem operací.

Mergesort

MERGESORT je snad nejstarší “chytrý” třídící algoritmus. Pracuje s frontou, do které na počátku nahází “předtříděné” rostoucí úseky, potom je v cyklu vybírá a jejich slití vrací zpátky, dokud nemá jen jednu posloupnost. Slití je vybrání vždy menšího na výstup a na konci dokopírování zbytků.

Jedna operace slití vyžaduje , jsou-li 2 posloupnosti dlouhé a prvků. První rozházení vyžaduje lineární čas, potom každé projití všech prvků slitím vyrábí posloupnosti délky , tedy počet projití všech prvků je a celková složitost . Je adaptivní na předtříděné posloupnosti a při omezeném počtu rostoucích úseků dosahuje lineární složitosti.

Quicksort

QUICKSORT je asi nejpoužívanější třídící algoritmus, v průměru má při rovnoměrném rozložení nejnižší očekávaný čas. Využívá techniky rozděl a panuj.

1. Vybere prvek (pivot).

2. Vytvoří posloupnosti prvků menších než a větších než .

3. Na ty sám sebe zavolá rekurzivně, do výsledku zapíše za sebe obě setříděné poloviny.

Procedura (bez rekurze) vyžaduje čas nebo v jednom běhu, tj. pro medián, kdyby , by měl celý algoritmus složitost . Medián lze nalézt v lineárním čase, ale pak by byly MERGESORT i HEAPSORT rychlejší, proto se jako bere např. první prvek posloupnosti.

Potom má procedura očekávaný čas , ale nejhorší případ , což je pro neznámé rozdělení dat nevhodné. Náhodná volba by celý běh také mohla dost zpomalit, proto se v praxi bere medián tří až pěti pevně zvolených prvků.

Očekávaný čas Quicksortu

Dva libovolné prvky jsou porovnávány maximálně jednou, a to když nebo je pivot a předtím ani jeden z nich pivot nebyl. Vezmeme si náhodnou veličinu , která má hodnotu , když QUICKSORT porovnal během výpočtu a z nějaké výsledné setříděné posloupnosti , a jinak. Potom , kde je pravděpodobnost porovnání. Potom celk. počet porovnání v celém běhu je

Pro výpočet uvažujeme “strom rekurze”, kde každý vrchol odpovídá jednomu rekurzivnímu volání procedury a s tím i nějaké podposloupnosti (do té už se sahá jen v jeho podstromě). V jeho levém podstromě jsou operace na úsecích prvků menších než pivot této posloupnosti a v pravém na větších . Přiřadíme každému vrcholu jeho pivot a očíslujeme vrcholy prohledáváním do šířky. Pak , když nebo je první pivot z množiny v tomto očíslování (protože kdyby to byl jiný prvek z této množiny, rozdělím a , aniž bych je porovnal; naopak prvky mimo tuto množinu coby pivoty od sebe a neoddělí). Množina má prvků, takže . Počet porovnání pak vyjde

Jednoduché třídění

- SELECTIONSORT třídí vybíráním nejmenšího prvku a jeho prohozením s levým krajním v nesetříděném úseku.

- INSERTSORT vkládá do setříděného úseku další prvek a postupným vyměňováním ho řadí na správné místo.

- SHELLSORT je jeho vylepšení – postupně INSERTSORTem třídí sekvence složené z každého -tého prvku pro klesající (sekvence klesajících musí být zvolena “šikovně”).

- BUBBLESORT – iterativně prochází posloupností a prohazuje inverze

- Jeho varianta SHAKESORT, která posloupnosti prochází tam a zpátky.

A-sort

Tento algoritmus je aplikací stromů v třídících algoritmech, vhodnou pro částečně předtříděné posloupnosti. Jinak proti klasickým algoritmům nemá žádné výhody. Pro algoritmus je nutné znát list s nejmenším prvekm FIRST, cestu k němu od kořene a pro každý list ukazatele na následující v uspořádání NEXT.

Postup: Odzadu (od “předtříděně největšího”) vkládat prvky do stromu modifikovaným A-INSERTem a pak přečíst posloupnost listů (jít po NEXT). A-INSERT pracuje tak, že místo pro vložení prvku hledá od FIRST (jde postupně nahoru po otcích a hledá, kde nejdřív může slézt zas k listům).

Složitost: Pomalejší než běžné třídění na libovolná data (asymptoticky stejné), ale rychlejší na částečně předtříděná. Vezmeme – počet inverzí v posloupnosti. Celk. potřebuju pro načtení prvků, pro všechna štěpení dohromady ze všech běhů A-INSERTu a na každé vložení pro nalezení místa, kde je výška, kam se z FIRST dostanu, přeskočím tak vrcholů (menších než vkládaný) a . Součet za dává:

Protože se nepoužívá DELETE, hodí se na toto stromy. Pro míru má složitost , v urč. případech i rychlejší než Quicksort.

Porovnání algoritmů

Algoritmus

Čas nejhůř

Čas

Porov. nejhůř

Porov.

PP

Paměť

AD

QUICKSORT

A

N

HEAPSORT

A

N

MERGESORT

N

A

A-SORT

A

A

SELECTIONSORT

A

N

INSERTSORT

N

A

je nějaká konstanta, značí počet inverzí v posloupnosti, PP – přímý přístup, AD – adaptivní na předtříděné.

Pro krátké posloupnosti je do délky vhodný SELECTIONSORT, do INSERTSORT, jinak QUICKSORT, což vede k hybridnímu algoritmu. Pro A-SORT jsou nejvhodnější -stromy. Poměr časů QUICKSORT, MERGESORT, HEAPSORT je v průměru , platilo to ale v roce 1984 :-).

Vylepšení Mergesortu

Nedosahuji optimálních výsledků, pokud slévané posloupnosti ve frontách nejsou přibližně stejně dlouhé. Proto provedu úvahu: mějme algoritmus, který slévá rostoucí posloupnosti a uvažujme jeho “slévací” strom (kde posloupnost odp. vrcholu (délky ) vznikne slitím posloupností z jeho synů). Součet časů pro MERGESORT je pak vnitřní vrchol list . Dále pracujeme jen s délkami posloupností, vytvoříme algoritmus OPTIM, který při slévání sumu minimalizuje – na začátku dá každé jednoprvkové posl. hodnotu , která odpovídá hodnotě jejího prvku (?). Pro slévání vybírá posloupnosti (stromy) s nejmenším a slitému stromu přiřadí . Nakonec zbyde v množině stromů jen jeden, a ten je optimální. Pro třídění fronty podle se používá BUCKETSORT. Celkem pracuje v čase na posloupnosti rostoucích úseků .

1.2 Přihrádkové třídění

Bucketsort (Counting sort)

Algoritmus BUCKETSORT třídí jen přirozená čísla z intervalu a to zavedením množin, do kterých je rozhází a nakonec tyto spojí do výsledku. Třídění je stabilní pro opakující se prvky, inicializace množin a projití při konkatenaci potřebují , rozházení prvků pak , takže celkem .

Varianta RADIXSORT umí třídit i ve větších intervalech, když používá BUCKETSORT na každou jednotlivou číslici. Protože BUCKETSORT je stabilní, bude to celé fungovat.

Hybrid Sort

Sofistikovanější verze HYBRIDSORT třídí reálná čísla z (a obecně tedy jakékoliv klíče). Má dané (počet přihrádek v poměru k ), rozhazuje do přihrádek a ty pak třídí haldou.

Nejhorší možný čas je , protože nejhůře se může stát, že všechny prvky nacpu do 1 přihrádky. Očekávaný čas pro nezávislé rovnoměrně rozdělené prvky je – pravděpodobnost velikostí množin se řídí binomickým rozdělením s parametrem , střední hodnota pak je:

Jak je vidět z odhadu, i kdybychom použili algoritmus s kvadratickou složitostí ve třídění jednotlivých přihrádek, zůstane očekávaná složitost lineární.

Wordsort

WORDSORT je modifikace BUCKETSORTu pro třídění slov. Příprava:

1. Rozhodí slova do množin podle jejich délky.

2. Vytvoří dvojice pozice-písmeno , kterou setřídí podle druhé složky BUCKETSORTem, výsledek setřídí podle první složky (stejně), tj. má seznam setříděných dvojic pozice-písmeno, které se ale mohou opakovat.

3. Dvojice rozstrká do množin pro každou pozici a odstraní duplicity.

Pak v hlavním cyklu postupuje od největší možné délky a pro každé pracuju jen s množinou slov délky :

1. Podle -tého písmena rozhodím všechna aktuálně tříděná slova do množin .

2. Potom podle množiny vyberu všechna neprázdná a sliju je za sebe.

3. Pro další krok přidávám kratší slova vždy na začátek množiny aktuálně tříděných.

Výpočet délek slov, inicializace a zařazení slov do vyžadují čas , kde je součet délek všech řetězců. Vytvoření seznamu dvojic a jeho třídění vyžaduje také . Založení a přeházení dvojic do nich také . Inicializace je , kde je velikost abecedy. V hlavním cyklu v každém kroku potřebuji dvakrát čas (součet délek slov dlouhých nebo víc). Celkem tedy .

1.3 Pořadové statistiky (hledání mediánu)

Vstupem je (neuspořádáná) posloupnost (navzájem různých) čísel. Výstup je -té, nebo obecně -té nejmenší číslo z nich. Složitost budeme měřit počtem porovnání.

Z dvou následujících FIND bývá rychlejší než SELECT pro většinu případů, ale nemá zaručenou asymptotickou složitost. Je známo, že medián lze nalézt na porovnání a že dolní odhad počtu porovnání je .

Hledání mediánu technikou rozděl a panuj (algoritmus FIND)

Tento algoritmus používá techniku “rozděl a panuj”. chová se podobně jako QUICKSORT a hledá obecně -té nejmenší číslo:

1. Vybrat pivota a rozdělit posloupnost pomocí porovnání na 3 oddíly: čísla menší než pivot ( prvků), pivota samotného a čísla větší než pivot ( prvků).

1. Pokud je , hledám rekurzivně -tý prvek v prvcích

2. Pokud je , vracím pivot

3. Pokud je , hledám rekurzivně -tý prvek v prvcích

Rekurzivní vzorec v nejhorším případě, což dává . Očekávaný čas odhadneme na a dokážeme indukcí podle z rekurzivního vzorce .

Zaručeně lineární hledání mediánu (algoritmus SELECT)

Vylepšení, garantující dobrý výběr pivota a lineární složitost i v nejhorším čase:

1. Rozdělit posloupnost na pětice (poslední může být neúplná, mějme threshold např. , pod kterým množinu přímo třídíme)

2. V každé pětici najít medián

3. Rekurzivně najít medián těchto mediánů

4. Použít ho jako pivot pro dělení celé posloupnosti, protože je větší než alespoň 3 prvky z alespoň pětic (až na zakrouhlení), je větší než alespoň prvků (a také menší než alespoň prvků)

5. Z toho mám vždy zaručeno, že zahodím alespoň prvků pro následující krok.

Vzorec potom vychází: a podle Master Theoremu nebo substituční metodou se dá vyčíslit jako .