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ů

### Třídění na vnější paměti

Algoritmus (Třídění sléváním (Mergesort))

Tento algoritmus se používá pro třídění dat, která se nevejdou do vnitřní paměti. Dá se použít i při sekvenčním přístupu k datovým souborům. Nejjednodušší verze bez bufferů vypadá takto:

- inicializace: na začátku každého kroku data rozdělí do 2 souborů
- načte 2 záznamy, každý z jednoho souboru a porovná je
- ve správném pořadí je zapíše do výstupního souboru, ze vstupního souboru si načte další dva
- v prvním kroku získám uspořádané posloupnosti délky 2; v dalších krocích vždy porovnám načtené prvky, zapíšu menší z nich a ze souboru odkud tento pocházel si načtu další, takže získám vždy uspořádané posloupnosti dvojnásobné délky než v předchozím kroku
- po krocích je soubor s záznamy setříděný.

Vylepšení se dosáhne např. přímo střídavým zapisováním výstupu do 2 souborů, kdy se zbavím nutnosti na začátku každého kroku data dělit, nebo použitím více souborů najednou. Je taky možné využít rostoucích posloupností prvků, které se v souboru nacházejí již před započetím třídění.

Algoritmus (Třídění haldou)

Pro třídění ve vnitřní paměti se používá algoritmus třídění haldou (heapsort), který se dá zakomponovat do vylepšení třídění sléváním (viz níže). Jeho základem je datová struktura halda (konkrétně maximální halda, max-heap), reprezentovaná jako pole záznamů, na kterém je binární stromová struktura: záznam má vždy vyšší klíč než jeho dva synové, nacházející se na pozicích a při číslování od 0 (pokud tato pozice není větší než velikost haldy, v opačném případě záznam nemá syny). Na pozici 0 se tak nachází záznam s nejvyšším klíčem. Postup třídění je následovný:

- největší prvek (z pozice 0) se prohodí s tím prvkem, jehož číslo pozice odpovídá aktuální velikosti haldy
- velikost haldy se zmenší o 1
- dokud neplatí podmínka, že klíč prvku získaného z konce haldy je větší než oba klíče jeho synů, prohazuje se tento se synem s větším klíčem (a tak posouvá v haldě dál)
- toto se opakuje, dokud je velikost haldy větší než 1, odzadu tak v poli vzniká setříděná posloupnost

Časová složitost algoritmu je pro pole záznamů velikosti .

Algoritmus (-cestné třídění)

Pokud mám k dispozici ve vnitřní paměti stránek, mohu postupovat následovně:

- v 1. kroku načíst do paměti stránek
- ty setřídit pomocí heapsortu (nebo i quicksortu apod.) a získat tak delší setříděné úseky (běhy)
- slévat vždy nejkratších běhů (pomocí mergesortu) a vytvářet tak jeden běh
- toto opakovat, dokud existuje více než 1 běh.

Čas. složitost pro stránek v souboru je .

Algoritmus (Dvojitá halda)

Delší běhy při slévání se dají vytvářet pomocí dvojité haldy - v paměti mám dvě haldy z celkem prvků, opakovaně z první haldy odebírám a zapisuji minimální prvek do výstupního běhu a načítám další prvek, pokud ten je větší než minimum haldy, vložím ho do prvé haldy, pokud je menší, vložím ho do druhé haldy, která vzniká od konce mého pole. Až se první halda vyčerpá, použiji druhou a začnu nový běh. Toto v nejhorším případě dává stejnou velikost běhů jako obyčejná halda, průměrně je 2x lepší.