Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Sekvenční třídění a porovnávací algoritmy

Pojmy sekvenční třídění a porovnávací algoritmy mohou znamenat vlastně cokoliv, takže uvedu pár nejběžnějších třídících algoritmů a budu doufat, že to bude ke zkoušce stačit `:-(`. Zdrojem mi budiž Wikipedie a kniha Algoritmy a programovací techniky Doc. P. Töpfera.

Algoritmus (Selection sort, třídění výběrem)

Selection sort je jeden z nejjednodušších třídích algoritmů. Jde o vnitřní třídění - tedy celá posloupnost prvků by měla být v paměti. Má časovou složitost a obecně bývá pomalejší než insertion sort. Pracuje následovně:

Udržuje si množinu setříděných prvků na začátku posloupnosti (pole), která je na začátku prázdná a na konci představuje celé pole. Zbytek pole za setříděnou množinou je neuspořádaný. V jednom kroku vždy vybere jeden prvek a vloží ho do utříděné části (kterou tím zvětší o 1 a zároveň zmenší nesetříděnou). Jeden krok algoritmu (kterých je pro prvků v každém případě) vypadá takto:

1. Najdi nejmenší prvek z nesetříděného úseku.
2. Vlož ho přesně za konec setříděného úseku (a prvek co tam byl původně si s ním vymění místo)

Heapsort, který popíšu později, může být považovaný za variantu selection sortu, protože také vybírá minimum a začleňuje do setříděné části.

Algoritmus (Insertion sort, třídění vkládáním)

Insertion sort je také relativně jednoduchý a na velké datové soubory neefektivní, ale jednoduchý na implementaci a rychlejší než nejprimitivnější algoritmy bubble sort a selection sort. Navíc je efektivní pro data, která jsou už částečně předtříděná - v nejhorším případě sice běží v čase , ale v nejlepším případě (úplné setřídění dat) je lineární - obecně běží v čase , kde je počet inverzí ve tříděné posloupnosti. Navíc je stabilní (zachovává pořadí prvků se stejným klíčem) a in-place, tedy nepotřebuje žádné pomocné datové struktury. Proti selection sortu ale většinou potřebuje více přepisování (a to může u velkých datových struktur vadit).

V jednom kroku vždy vezme nějaký prvek (berou se po řadě od začátku pole), zapamatuje si jeho hodnotu, a dokud před ním jsou prvky s větším klíčem, posouvá je na pozici o 1 větší (čímž vždy přepíše následující, takže původní prvek se ztratí) a pokud narazí na prvek s menším klíčem, do za něj napíše onen zapamatovaný prvek (a místo tam je, protože celou cestu k němu posouval prvky). Algoritmus vypadá takto:

    insert sort( array a ){
    for( i = 1; i < a.length - 1; ++i ){
    value = a[i];
    j = i-1;
    while( j >= 0 && a[j] > value ){
    a[j + 1] = a[j];
    j = j-1;
    }
    a[j+1] = value;
    }
    }

Jednou z variant insertion sortu je Shell sort, který porovnává prvky ne vedle sebe, ale vzdálené o nějaký počet polí, který se postupně zmenšuje. Může dosahovat složitost až . S jistými úpravami se u něj dá dosáhnout až . Jiné vylepšení je library sort, který si při vkládání nechává mezery pro další prvky (podobně jako v knihovně nejsou poličky úplně plné) - ten může s velkou pravděpodobností běžet v čase , ale zase potřebuje větší paměťový prostor.

Algoritmus (Bubble sort, bublinkové třídění)

Bubble sort je velmi jednoduchý třídící algoritmus (asi nejjednodušší na implementaci), s časovou složitostí . V nejlepším případě (pro úplně setříděná data) mu ale stačí jen jeden průchod, takže . Většinou ale bývá pomalejší i než insertion sort, takže se na velké množiny dat nehodí.

Algoritmus prochází v jednom kroku celé pole a hledá pozice, kde se prvek s menším klíčem nachází bezprostředně za prvkem s větším klíčem. Takovéto dva prvky pak vymění. Kroky opakuje, dokud neprojde celé pole bez jediného prohození prvků (nebo v tupější variantě -krát pro prvků, protože pak je zaručeno, že posloupnost bude pro libovolné pořadí prvků setříděná - ta má ale pak složitost v každém případě!).

Vylepšení algoritmu lze dosáhnout jednoduchou úvahou: největší prvek je už při prvním průchodu polem odsunutý až na konec. To se samozřejmě opakuje pro každý průchod (ve druhém je předposlední na druhém místě od konce atp.), takže lze průchody postupně zkracovat a konec pole už netestovat - dosáhneme tím v průměru dvojnásobné rychlosti.

Variantou bubble sortu je shake sort neboli cocktail sort, který střídavě prochází posloupnost prvků nejdřív od začátku a pak od konce (a přitom provádí to samé jako bubble sort). Tím může v některých případech o trochu třídění zrychlit - příkladem budiž posloupnost prvků , která potřebuje jen 1 průchod cocktail-sortem tam a jeden zpět, ale pro bubble-sort by potřebovala 4.

Dalším vylepšením bubble sortu je Comb sort, který o něco zvyšuje rychlost. Je založen na stejné myšlence jako shell sort - tedy nejsou porovnávány prvky bezprostředně za sebou, ale prvky posunuté o nějaký ofset - ten je na začátku roven délce posloupnosti, a postupně se dělí zkracovacím faktorem (běžná hodnota ) až dosáhne jedné. Složitost se pohybuje mezi v nejhorším případě a v nejlepším. V průměrném případě jde stále o , ale s menší konstantou než u bubble-sortu (TODO: tohle je potřeba set-sakra ověřit ... opsané z německé wiki a talk:Comb sort na anglické, takže fakt důvěryhodné).

Algoritmus (Heap sort, třídění haldou)

Heapsort je také třídící algoritmus založený na porovnávání a myšlenkově vychází ze selection sortu, ke kterému přidává práci s haldou. Většinou bývá pro typická vstupní data pomalejší než quicksort, ale zaručuje časovou složitost i v nejhorším případě. Jde o in-place algoritmus (halda se může nacházet přímo v nesetříděné části pole), ale není stabilní.

Algoritmus sám, máme-li vyřešené operace na haldě, je velice jednoduchý - nejdříve pro každý prvek opakuje jeho vložení do haldy (takže postupně vytvoří -prvkovou haldu, která se s každým krokem zvětšuje o 1), pro implementaci haldy na začátku pole je vhodný max-heap, a potom opakuje odebrání maxima a jeho přesun na volné místo hned za konci zmenšivší se haldy - takže od konce pole postupně roste směrem k začátku setříděná posloupnost.

Upravený heapsort s použitím ternární haldy dosahuje o multiplikativní konstantu lepší výsledky, existuje i (prý :-)) složitá varianta smoothsort, která se blíží časové složitosti , pokud jsou data částečně předtříděná - heapsort totiž pracuje pro libovolnou posloupnost v čase .

Algoritmus (Merge sort, třídění sléváním)

Dalším třídícím algoritmem založeným na porovnávání prvků je mergesort. Je stabilní, takže zachovává pořadí dat se stejným klíčem. Jde o příklad algoritmu typu rozděl a panuj, stejně jako u níže popsaného quicksortu. Byl vynalezen Johnem Von Neumannem. Je založen na rozdělení posloupnosti na dvě zhruba stejné poloviny, rekurzivním setřídění a potom slévání dvou již setříděných posloupností. Jeho časová složitost je i v nejhorším případě, provádí většinou méně porovnání než quicksort, má větší nároky na paměť v případě rekurzivního volání (existuje ale i nerekurzivní verze), ale většinou nepracuje na místě a potřebuje alokovat paměť pro výstup setříděných posloupností (i toto se dá odstranit, ale je to zbytečně složité a přílišné zrychlení oproti použití jiného algoritmu nepřinese). Jeho přístup ho ale činí ideálním k použití na médiích se sekvenčním přístupem k datům (např. pásky). Jde tedy použít i ke třídění na vnější paměti - detaily viz sekce o databázích.

Postup práce je následující:

1. Rozděl nesetříděnou posloupnost na dvě (zhruba) poloviční části
2. Pokud mají více než jeden prvek, setřiď je rekurzivním zavoláním mergesortu (tj. pro každou z nich pokračuj od kroku 1 do konce algoritmu), jinak pokračuj následujícím krokem.
3. Slij dvě setříděné posloupnosti do jedné - vyber z obou posloupností první prvek, a pak opakovaně prvky porovnávej, zapisuj do setříděné posloupnosti menší z nich a doplňuj dvojici z té poloviční posloupnosti, odkud pocházel zapsaný prvek.

Algoritmus (Quicksort)

Quicksort je jedním z nejrychlejších algoritmů pro třídění na vnitřní paměti, přestože v nejhorším případě může jeho časová složitost dosáhnout až . Pro ideální i průměrná data dosahuje . Je také založen na principu rozděl a panuj, i když poněkud jiným způsobem než předchozí zmiňovaný, od něhož se liší i tím, že není stabilní.

Algoritmus nejdřív vybere nějaký prvek, tzv. pivot, a prvky s klíčem větší než pivot přesune do jiné části pole než ty s klíčem menším. Pak rekurzivně třídí obě části pole - když se dostane k polím délky 1, problém je vyřešen. Postup vypadá takto:

1. Vyber pivot (jeden prvek ze seznamu). Tady jde o největší magii, protože k dosažení nejlepší rychlosti by se měl pokaždé vybírat medián. Nejjednodušší je vybrat první, ale tento výběr ovlivňuje výslednou rychlost práce, takže se vyplatí např vzít tři prvky, porovnat je a vzít si z nich ten prostřední.
2. Postupuj od začátku pole a hledej první prvek větší nebo rovný než pivot. Až ho najdeš, postupuj od konce a najdi první prvek menší než pivot.
3. Prvky prohoď a opakuj krok 2 a 3, dokud se hledání od začátku a od konce nepotká na nějaké pozici - tu pojmenujeme třeba .
4. Rekurzivním voláním setřiď prvky a (má-li tříděné pole délku ) - to znamená pro obě části pole pokračuj od kroku 1. Pokud je nebo , není třeba už rekurzivního volání, protože posloupnosti délky 1 jsou setříděné.

Pro algoritmus existuje i nerekurzivní verze (stačí rekurzi nahradit zásobníkem úseků čekajících na zpracování). Je vidět, že na volbě pivotu závisí všechno - pokud pokaždé jako pivot volím 1. nebo . hodnotu v poli v pořadí podle velikosti, dělím pak vždy na části o délce 1 a , takže tento rekurzivní krok provedu až -krát a dostanu se k času . Samozřejmě, díky existenci algoritmu pro nalezení mediánu v čase je možné i tady dosáhnout zaručené složitosti , ale v praxi je to kvůli vysoké multiplikativní konstantě nepoužitelné - k výběru pivotu se většinou s úspěchem užívá nějaká jednoduchá heuristika, jak je nastíněno v popisu algoritmu samotného.

Heapsort bývá pomalejší než quicksort, ale zaručuje nízkou časovou složitost i pro nejhorší případ a navíc potřebuje méně paměti - nároky quicksortu navíc (kromě tříděné posloupnosti) jsou minimálně, kvůli nutnosti použití rekurzivního volání nebo zásobníku. Oproti mergesortu ho nelze použít na data se sekvenčním přístupem, tyto nevýhody ale vyvažuje relativní jednoduchostí implementace a rychlostí v průměrném případě.

Variantou quicksortu je introsort, který ho kombinuje s heapsortem, pokud hloubka rekurze dosáhne nějakých nepřijatelných hodnot - tak je zaručena časová složitost i v nejhorším případě (samozřejmě je to ale v nejhorším případě pořád pomalejší než použití jen heapsortu). Jedna z variant tohoto algoritmu se dá použít k hledání -tého nejmenšího prvku (tedy i mediánu), kdy dosahuje složitosti průměrně až nejhůře.