Algoritmy I Třídění
1
ALGI 2010/2011
Třídící problém • Je dána množina A = {a1 ,a2 ,...,an }. Je potřebné najít permutaci π těchto n prvků, která zobrazuje danou posloupnost do neklesající posloupnosti aπ(1), aπ(2), ... ,aπ(n) tak, že aπ(1) ≤ aπ(2) ≤ ... ≤ aπ(n) . • Množinu U, ze které vybíráme prvky tříděné množiny, nazýváme univerzum.
2
ALGI 2010/2011
Třídící problém • Prvky množiny U se nazývají klíče a informace vázaná na klíč spolu s klíčem se nazývá záznam. • Jestliže je velikost vázané informace příliš velká je výhodnější utřídit jen klíče s patřičnými odkazy na vázané informace, které se v tomto případě nehýbají. Bez újmy na obecnosti budeme dále předpokládat, že třídíme pouze klíče.
3
ALGI 2010/2011
Vlastnosti třídících metod • Třídící metoda se nazývá stabilní, když zachovává relativní uspořádání záznamů se stejným klíčem. To znamená, že pro třídící permutaci platí: π(i)<π(j) ⇔ aπ(i) = aπ(j) pro 1≤ i < j ≤ n. • Stabilita třídění je často důležitá tehdy, když jsou prvky již uspořádané podle určitých sekundárních klíčů, to znamená vlastností, které samotný (primární) klíč neodráží. 4
ALGI 2010/2011
Vlastnosti třídících metod • Třídící algoritmus nazýváme přirozeným, jestliže jeho složitost roste resp. klesá v závislosti na míře setříděnosti vstupní posloupnosti – tj. jestliže doba potřebná k setřídění již setříděné podmnožiny údajů je menší, než doba potřebná na setřídění zbývající nesetříděné podmnožiny. • Pokud tato podmínka není splněna, pak se metoda označuje za nepřirozenou.
5
ALGI 2010/2011
Vlastnosti třídících metod • Třídění se nazývá in situ (neboli na původním místě), jestliže třídící algoritmus vyžaduje, kromě vlastního tříděného pole, pomocnou paměť pouze konstantního rozsahu. • Jinými slovy algoritmus nepoužívá žádnou další paměť, jejíž velikost by byla závislá na rozsahu tříděných hodnot (např. další pole rozsahu n).
ALGI 2010/2011
6
Klasifikace třídících algoritmů • Při vnitřním třídění máme větší volnost při výběru vhodných datových struktur (pole, seznamy, stromy,….) a operací nad nimi. • Naopak při vnějším třídění musíme vystačit jen se sekvenčním přístupem k prvkům tříděné množiny, a tedy třída přípustných algoritmů je oproti předcházejícímu případu značně omezená.
ALGI 2010/2011
7
Složitost třídících algoritmů • Složitost algoritmů bude dána počtem provedených významných operací. – Pro vnitřní třídění považujeme za významné operace porovnávání klíčů a přesuny prvků. – U vnějšího třídění hrají klíčovou roli operace přístupu do datových souborů.
8
ALGI 2010/2011
ALGI Asociativní třídění
9
ALGI 2010/2011
Třídění přímým vkládáním (Insertion Sort) • Tento způsob třídění připomíná řazení karet. • Postupně vybíráme jednu kartu za druhou a zařazujeme je na odpovídající místo podle barvy a hodnoty - klíče, ostatní ještě nezatříděné posuneme o jednu pozici.
10
ALGI 2010/2011
Třídění přímým vkládáním •
Algoritmus: 1. První prvek pole ponecháme na svém místě. 2. Vezmeme druhý prvek a porovnáme jej s prvním. Je-li menší, zařadíme ho na první místo a první prvek posuneme, jinak je ponecháme na místě. 3. Vezmeme třetí prvek a porovnáme jej s prvními dvěma prvky. Je-li menší než některý z nich, zařadíme jej na odpovídající pozici a následující prvky podle potřeby posuneme. Jinak je ponecháme na původních místech. 4. Obdobně postupujeme i s ostatními prvky v poli.
11
ALGI 2010/2011
Př: Je dána posloupnost čísel 11 3 27 8 50 22 12. Setřiďte ji metodou přímého vkládání. 11 3 3 3 3 3 3 12
3 11 11 8 8 8 8
27 27 27 11 11 11 11
8 8 8 27 27 22 12
50 50 50 50 50 27 22
22 22 22 22 22 50 27
12 12 12 12 12 12 50 ALGI 2010/2011
Složitost • Nejhorší případ nastává, jestliže zdrojová posloupnost je uspořádána v opačném pořadí. • Počet porovnání pro i-tý prvek bude Ci = i-1 a počet přesunů Mi = Ci+2. • Celkový počet porovnání Cmax a přesunů Mmax pro nejhorší případ bude
N2 − N = ∑ Ci = 2 i =2 N
Cmax
N 2 + 3N − 4 = ∑ Mi = 2 i =2 N
M max
• Složitost metody přímým vkládáním je tedy O(N2).
13
ALGI 2010/2011
Třídění přímým výběrem (Selection Sort) • Pro jednoduchost si představme posloupnost rozdělenou do dvou částí. • V jedné části jsou již setříděné prvky, zatímco druhá část je nesetříděná. • V nesetříděné části najdeme nejmenší prvek a přesuneme ho na konec setříděné části (vyměníme s posledním prvkem setříděné části).
ALGI 2010/2011
14
Třídění přímým výběrem •
Algoritmus: 1. V posloupnosti najdeme nejmenší prvek a vyměníme ho s prvkem na první pozici. Tím dojde k rozdělení posloupnosti na dvě části. Setříděná část obsahuje pouze jeden prvek, nesetříděná N-1. 2. V nesetříděné části najdeme nejmenší prvek a vyměníme ho s prvním prvkem v nesetříděné části, čímž dojde k zařazení tohoto prvku do setříděné části. 3. Obsahuje-li nesetříděná část více než jeden prvek, pokračujeme bodem 2, jinak je třídění ukončeno.
ALGI 2010/2011
15
Př: Je dána posloupnost čísel 11 3 27 8 50 22 12. Setřiďte ji metodou přímého výběru. 11 3 3 3 3 3 3 ALGI 2010/2011
3 11 8 8 8 8 8
27 27 27 11 11 11 11
8 8 11 27 12 22 12
50 50 50 50 50 22 22
22 22 22 22 22 50 27
12 12 12 12 27 27 50 16
Složitost N2 − N C= 2
M max
N2 ≅ + 3( N − 1) 4
• Složitost metody přímým výběrem je tedy O(N2).
ALGI 2010/2011
17
Bublinkové třídění (Bubble Sort) • Třídění přímou výměnou sousedních prvků. Procházíme polem, porovnáváme dva sousední prvky a pokud nejsou v požadovaném pořadí, prohodíme je.
ALGI 2010/2011
18
Bublinkové třídění •
Algoritmus: 1. Posloupnost rozdělíme na dvě části, setříděnou a nesetříděnou.Setříděná část je prázdná. 2. Postupně porovnáme všechny sousední prvky v nesetříděné části a pokud nejsou v požadovaném pořadí, prohodíme je. 3. Krok 2 opakujeme tak dlouho, dokud nesetříděná část obsahuje více než jeden prvek. Jinak algoritmus končí.
ALGI 2010/2011
19
Př: Je dána posloupnost čísel 11 3 27 8 50 22 12. Setřiďte ji metodou Bubble Sort. 11 3 3 3 3 3 3 ALGI 2010/2011
27 11 8 8 8 8 8
8 27 11 11 11 11 11
50 8 27 12 12 22 12
22 50 12 27 22 22 22
3 22 50 22 27 27 27
12 12 22 50 50 50 50 20
Modifikace kroku 3 (Přirozené bublinkové třídění): Pokud nastala v kroku 2 alespoň jedna výměna, došlo ke zmenšení nesetříděné části o jeden prvek, pokračujeme bodem 2. Jinak je třídění ukončeno.
11 3 3 3 3 3 ALGI 2010/2011
27 11 8 8 8 8
8 27 11 11 11 11
50 8 27 12 12 22
22 50 12 27 22 22
3 22 50 22 27 27
12 12 22 50 50 50 21
Složitost • Počet porovnání je v jednotlivých krocích bude Ci = N-i a Počet přesunů v i-tém kroku je Mi = 3(N-i). • Celkem tedy N2 − N C = ∑ Ci = 2 i =2 N
3( N 2 − N ) M = ∑ Mi = 2 i =2 N
• Složitost metody přímým vkládáním je tedy O(N2).
ALGI 2010/2011
22
Přetřásání (Shaker Sort) • Jde o modifikaci algoritmu bublinkového třídění, kdy střídáme porovnávání prvků z hlediska uspořádání. Při průchodu posloupností z jedné strany provádíme porovnávání pro relaci uspořádání ≤, z druhé strany pak pro relaci uspořádání ≥. • Ani úpravou bublinkového třídění se nesnížil řádový odhad, složitost zůstává stále O(N2).
ALGI 2010/2011
23
Př: Je dána posloupnost čísel 11 3 27 8 50 22 12. Setřiďte ji metodou Shaker Sort. 11 3 3 3 3 3 3 ALGI 2010/2011
27 11 11 8 8 8 8
8 27 8 11 11 11 11
50 8 27 12 12 12 12
22 50 22 27 22 22 22
3 22 12 22 27 27 27
12 12 50 50 50 50 50 24
Rychlé třídění (Quick Sort) • Metoda Quick-sort je založena na principu rozdělení tříděného pole na dva disjunktní úseky U1 a U2 (v souladu s metodou divide-et-impera) přibližně stejné velikosti, pro které musí platit ∀x∈U1, y∈U2, platí x ≤ y v případě vzestupného třídění. • Každá množina se potom rekurzívně dotřídí. • Závěrečný syntetizační krok je triviální spočívá ve spojení setříděných posloupností. ALGI 2010/2011
25
Rychlé třídění (Quick Sort) •
•
Algoritmus: Zvolíme prvek x (pivot). Pole začneme prohledávat jak od začátku, tak od konce. Pro všechny prvky ai, které porovnáváme s x směrem od začátku musí platit, že ai < x. Naopak, pro všechny prvky aj, které porovnáváme s x směrem od konce musí platit, že aj > x. Jakmile narazíme na dvojici ai a aj, která nesplňuje výše uvedenou podmínku, prvky ai a aj zaměníme. Takto postupujeme dokud i ≤ j. Ve chvíli, kdy i > j platí, že pole je rozděleno do dvou úseků U1 a U2, přičemž úsek U1 zahrnuje prvky od začátku pole až po prvek na pozici j, U2 pokračuje od i až do konce pole. Úseky U1 a U2 opět třídíme metodou Quick Sort. Třídění je ukončeno ve chvíli, kdy délka všech setříděných úseků je 1.
ALGI 2010/2011
26
Př: Je dána posloupnost čísel 6 55 12 42 94 18 44 67. Setřiďte ji metodou Quick Sort.
6 6 6 6 6 6
ALGI 2010/2011
55 18 12 12 12 12
12 12 18 18 18 18
42 42 42 42 42 42
94 94 94 94 44 44
18 55 55 55 55 55
44 44 44 44 94 67
27
67 67 67 67 67 94
Rychlé třídění (Quick Sort) • Složitost algoritmu: – Značně se liší pro nejlepší a nejhorší případ. – Složitost není ovlivněna pořadím prvků před tříděním, ale volbou prvku x. – Nejlepší případ nastane tehdy, když volba x vždy padne na tzv. medián, který rozdělí pole na dva stejně velké úseky. Počet dělení pro získání úseků délky 1 je pak přibližně log2(N) a složitost celé metody je O(N log2 (N)). – Nejhorší případ nastane, když jako prvek x pokaždé zvolíme nejmenší nebo největší prvek tříděného úseku. Pole se vždy rozdělí na dva úseky - jeden úsek bude obsahovat volený prvek x, druhý ostatní prvky tříděného úseku. V tomto případě se bude provádět N-1 dělení, takže výsledná složitost je řádu O(N2).
ALGI 2010/2011
28
Rychlé třídění (Quick Sort) • Praktické testy ukázaly, že Quick Sort je velice rychlý při třídění rozsáhlých polí, ale zaostává oproti přirozeným algoritmům třídění Insert Sort a Select Sort při třídění malých polí. • Ukazuje se, že složitost Quick Sortu má jistou minimální hodnotu, pod kterou i při třídění malého počtu prvků neklesne. Kdežto složitost přirozených algoritmů roste úměrně s počtem tříděných prvků. • Jinými slovy do jistého počtu prvků má Quick Sort větší režii (třídí pomaleji) než např. Insert Sort. Tato hranice byla experimentálně stanovena na asi 12 prvků. Vyplatilo by se tedy Quick Sortem třídit rozsáhlé pole, ale jakmile úseky na než se pole dělí budou kratší než zvolená mez (řekněme zmíněných 12 prvků), tento krátký úsek dotřídit Insert Sortem. ALGI 2010/2011
29
Vlastnosti uvedených algoritmů • Selection Sort – metoda je stabilní a přitozená • Bubble Sort – metoda je stabilní a přirozená • Insertion Sort – metoda je stabilní a přirozená • Quick Sort - metoda je nestabilní!
ALGI 2010/2011
30
Třídění vkládáním s ubývajícím krokem (Shell Sort) • Jednoduchý, ale přitom geniální algoritmus popsal D. L. Shell v roce 1959, když navrhl využít třídění vkládáním ve více chodech. V i-tém chodu se třídí prvky ležící ve vzdálenosti hi, pro i=t, t-1,…,0, hi+1> hi, h1= 1, t > 0. Číslo hi se nazývá i-tý krok metody. • Takto dostaneme v závislosti na volbě kroků celou třídu třídících algoritmů. • Tyto algoritmy fungují efektivně, protože v počátečních chodech se třídí relativně krátké posloupnosti a v dalších chodech se třídí delší, ale utříděnější posloupnosti.
ALGI 2010/2011
31
Př: Je dána posloupnost čísel 44 18 12 42 94 55 6 67. Setřiďte ji metodou Shell Sort 44 44 44 6 6 6
ALGI 2010/2011
55 18 18 18 18 12
12 6 6 12 12 18
42 42 42 42 42 42
94 94 94 44 44 44
18 55 55 55 55 55
6 12 12 94 94 67
67 67 67 67 67 94
32
Shell Sort • •
•
Intuitivně je zřejmé, že složitost Shellova algoritmu bude záviset na volbě posloupnosti kroků. Mezi nejznámější návrhy patří tyto posloupnosti kroků: A. h1=1 , hi+1 =2*hi+1 B. h1=1 , h2 =2 , hi+1=2*hi-1 (pro i > 2), O(N (log N)2). C. h1=1 , hi+1=3*hi+1 (364, 121, 40, 13, 4, 1 pro 1000 prvků), O(N3/2). Podrobná matematická analýza volby optimální posloupnosti však patří k nevyřešeným problémům. Jsou známé jen některé částečné výsledky.
ALGI 2010/2011
33
Poznámka • Algoritmy asociativního třídění používají pro určení pozice prvku v tříděné množině S jen relativní hodnoty prvků, které určují vzájemným porovnáváním těchto prvků. • Algoritmy adresního třídění (viz dále) využívají jednoznačný vztah mezi absolutními hodnotami prvků z U a jejich pozicí v uspořádané množině. Pro výpočet tohoto vztahu můžeme použít libovolné operace mimo porovnání tříděných prvků. ALGI 2010/2011
34
Adresní třídící algoritmy • Tyto algoritmy nepoužívají při své činnosti žádnou preferovanou operaci. Proto za míru časové efektivnosti zvolíme celkový počet operací vykonaných po dobu třídění. • Adresní třídění se podobá uklízení např. rozházených dětských hraček: když o každé hračce víme, na které místo patří, stačí ji jen vzít a dát na své místo.
ALGI 2010/2011
35
Přihrádkové třídění • Přihrádkové třídění je základním algoritmem adresního třídění. Většinou slouží jako základ pro konstrukci složitějších algoritmů adresního třídění. • Nechť aπ(1), aπ(2), ... ,aπ(n) je posloupnost celých čísel z ohraničeného univerza U={0,…,m-1} (některá z čísel ai mohou být stejná). Když m není příliš veliké, potom je možné posloupnost efektivně utřídit touto metodou: ALGI 2010/2011
36
Přihrádkové třídění •
Algoritmus: 1. Inicializace: inicializuj m prázdných seznamů (přihrádek), pro každé číslo i ∈ {0,…,m-1} jeden seznam; 2. Distribuce: čti posloupnost zleva doprava, a prvek ai umísti do ai -tého seznamu, na jeho konec (tj. seznamy se chovají jako fronty); 3. Zřetězení: zřetězit všechny seznamy tak, že začátek (i+1)-ního seznamu se připojí na konec itého.
ALGI 2010/2011
37
Přihrádkové třídění •
•
Tak vznikne jediný seznam obsahující prvky v utříděném pořadí. Protože jeden prvek je možné zařadit do i-tého seznamu v konstantním čase, n prvků v čase O(n). Zřetězení m seznamů si vyžaduje čas O(m), takže celková složitost přihrádkového třídění je O(m+n). Tento druh třídění se používá zejména tehdy, když m << n. Potom je jeho složitost lineární. Třídění sice není in situ, ale je stabilní.
ALGI 2010/2011
38
Přihrádkové třídění - příklad •
Mějme například realizovat funkci, která načte jednotlivé znaky ze souboru InputName a vypíše je setříděné do souboru OutputName. Celý problém lze naprogramovat velice jednoduše využitím zjednodušené verze přihrádkového třídění. – – –
Vytvoříme pole 256 počítadel - pro každý znak jedno - na počátku je nastavíme na 0. Potom čteme vstupní soubor a příslušné počítadlo inkrementujeme. Nakonec vypíšeme do výstupního souboru tolik znaků, na kolik jsou jednotlivá počítadla nastavena, to znamená, že nejprve vypíšeme například 20 znaků a, potom 10 znaků c, 1 znak f atd.
ALGI 2010/2011
39
Přihrádkové třídění - příklad • Mějme dánu posloupnost písmen sortingexample • Po setřídění dostaneme posloupnost aeegilmnoprstx
ALGI 2010/2011
40
Třídění podle základu (Radix Sort) • Klíče užívané k definování pořadí záznamů jsou v mnoha případech velice komplikované. Například klíče užívané pro třídění v katalozích knihoven. • Proto je vhodné postavit třídicí metody na porovnání dvou klíčů a výměně dvou záznamů. • Pro mnoho aplikací je možno využít faktu, že klíč lze považovat za číslo jistého rozsahu. Třídící metoda založená na této myšlence se nazývá Radix Sort. Tento algoritmus neporovnává dva klíče, nýbrž zpracovává a porovnává části klíčů.
ALGI 2010/2011
41
Třídění podle základu (Radix Sort) • Radix Sort považuje klíče za čísla zapsaná v číselné soustavě o základu M (radix) a pracuje s jednotlivými číslicemi. • Představme si úředníka, který má setřídit hromadu karet, přičemž na každé kartě je natištěno tříciferné číslo. – Jeden z rozumných postupů je asi tento: vytvořit deset hromádek, na první dávat karty s čísly menšími než 100, na druhou karty s čísly 100 až 199 atd. – Každou z těchto deseti hromádek pak znovu roztřídit stejným způsobem nebo pokud je na hromádce karet málo, setřídit je jednoduchým způsobem. – Popsaná metoda, je jednoduchou ukázkou Radix Sortu o základě M=10.
• Pro počítač je logicky lepší pracovat se základem M=2. ALGI 2010/2011
42
Př.: Je dána posloupnost COW DOG SEA RUG ROW MOB BOX TAR BAR EAR TAB DIG BIG TEA NOW FOX. Setřiďte ji metodou Radix Sort Po 1. kroku setřídění podle 1.znaku (výpis kromě prázdných přihrádek) B: BOX BAR BIG C: COW D: DOG DIG E: EAR F: FOX M: MOB N: NOW R: RUG ROW S: SEA T: TAR TAB TEA ALGI 2010/2011
Po 2.kroku setřídění podle 2. znaku : B: C: D: E: F: M: N: R: S: T:
BAR COW DIG EAR FOX MOB NOW ROW SEA TAR
BIG BOX DOG
RUG TAB TEA 43
Po 3. kroku setřídění podle 3. znaku: B: C: D: E: F: M: N: R: S: T:
BAR COW DIG EAR FOX MOB NOW ROW SEA TAB
BIG BOX DOG
RUG TAR TEA
BAR BIG BOX COW DIG DOG EAR FOX MOB NOW ROW RUG SEA TAB TAR TEA ALGI 2010/2011
44
Radix sort • Princip implementace: – Předpokládejme, že přeskupujeme záznamy v poli tak, že záznamy jejichž klíče začínají bitem 0 předcházejí záznamy s klíči začínajícími bitem 1. Tato úvaha vede na rekurzivní třídící algoritmus typu QuickSort: jestliže jsou dvě části pole setříděny, potom je setříděno i celé pole. Při výměnách záznamů v poli postupujeme zleva a hledáme klíč začínající na 1, stejně tak zprava hledáme klíč začínající na 0. Tyto záznamy vyměníme a pokračujeme dokud se indexy testovaných záznamů uprostřed pole nepřekříží. – Tato implementace je velice podobná QuickSortu, s tím rozdílem, že jako pivot je použito číslo 2b místo nějakého prvku z pole.
ALGI 2010/2011
45
Radix sort • Složitost: – určení složitosti v porovnání s asociatvními algoritmy není tak jednoduché. Více než počet klíčů (vstupních dat) nás musí zajímat počet bajtů klíče a základu (čísla 2b). – Nejhorší případ znamená prozkoumat všechny bajty všech klíčů.
ALGI 2010/2011
46
