V tomto článku se budeme zabývat důležitými vlastnostmi různých třídicích technik včetně jejich složitosti, stability a paměťových omezení. Před pochopením tohoto článku byste měli porozumět základům různých třídicích technik (viz : Třídicí techniky).
Analýza časové složitosti –
Probrali jsme nejlepší, průměrnou a nejhorší složitost různých třídicích technik s možnými scénáři.
Třídění založené na porovnávání –
Při třídění založeném na porovnávání se prvky pole navzájem porovnávají, aby se našlo setříděné pole.
- Bubble sort a Insertion sort –
Průměrná a nejhorší časová složitost: n^2
Nejlepší časová složitost: n, když je pole již setříděno.
Nejhorší případ: když je pole zpětně setříděné. - Selekční třídění –
Nejlepší, průměrná a nejhorší časová složitost: n^2, která je nezávislá na rozložení dat. - Slučovací třídění –
Nejlepší, průměrná a nejhorší případ časové složitosti: nlogn, který je nezávislý na rozložení dat. - Řazení na hromadu –
Nejlepší, průměrná a nejhorší případ časové složitosti: nlogn, který je nezávislý na rozložení dat. - Rychlé třídění –
Jedná se o přístup „rozděl a panuj“ s rekurenční relací:T(n) = T(k) + T(n-k-1) + cn
Nejhorší případ: když je pole seřazeno nebo zpětně seřazeno, rozdělovací algoritmus rozdělí pole na dvě podpole s 0 a n-1 prvky. Proto,
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
Nejlepší případ a průměrný případ: V průměru rozdělí algoritmus rozdělení pole na dvě podpole o stejné velikosti. Proto,
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Třídění bez porovnávání –
Při třídění bez porovnávání se prvky pole mezi sebou neporovnávají, aby se našlo seřazené pole.
- Radix sort –
Nejlepší, průměrná a nejhorší časová složitost: nk, kde k je maximální počet číslic v prvcích pole. - Count sort –
Nejlepší, průměrná a nejhorší časová složitost: n+k, kde k je velikost počítaného pole. - Bucket sort –
Nejlepší a průměrná časová složitost: n+k, kde k je počet bucketů.
Časová složitost v nejhorším případě: n^2, pokud všechny prvky patří do stejného bucketu.
In-place/Outplace technika –
Třídicí technika je inplace, pokud nepoužívá k třídění pole žádnou paměť navíc.
Mezi diskutovanými technikami založenými na porovnávání je pouze slučovací třídění technikou outplaced, protože vyžaduje další pole pro sloučení tříděných dílčích polí.
Mezi diskutovanými technikami, které nejsou založeny na porovnávání, jsou všechny techniky outplaced. Počítací třídění používá počítací pole a kbelíkové třídění používá pro třídění pole hašovací tabulku.
Třídicí technika online/offline –
Třídicí technika je považována za online, pokud může přijímat nová data během probíhající procedury, tj. pro zahájení třídicí operace nejsou vyžadována kompletní data.
Mezi diskutovanými technikami založenými na porovnávání splňuje tyto podmínky pouze třídění vkládáním, a to kvůli základnímu algoritmu, který používá, tj. že zpracovává pole (nikoliv jen prvky) zleva doprava, a pokud jsou vpravo přidány nové prvky, nemá to vliv na probíhající operaci.
Stabilní/nestabilní technika –
Třídicí technika je stabilní, pokud nemění pořadí prvků se stejnou hodnotou.
Z technik založených na porovnávání jsou stabilními technikami bublinkové třídění, vkládací třídění a slučovací třídění. Selekční třídění je nestabilní, protože může změnit pořadí prvků se stejnou hodnotou. Uvažujme například pole 4, 4, 1, 3.
V první iteraci je nalezen minimální prvek 1 a je prohozen se 4 na 0. pozici. Proto se změní pořadí 4 vzhledem ke 4 na 1. pozici. Podobně jsou nestabilní i quick sort a heap sort.
Z technik nezaložených na porovnávání jsou stabilními třídicími technikami Counting sort a Bucket sort, zatímco stabilita radix sort závisí na základním algoritmu použitém pro třídění.
Analýza třídicích technik :
- Když je pole téměř setříděné, lze upřednostnit vkládací třídění.
- Když není známo pořadí vstupu, upřednostňuje se slučovací třídění, protože má v nejhorším případě časovou složitost nlogn a je také stabilní.
- Když je pole setříděné, vkládací a bublinkové třídění dává složitost n, ale rychlé třídění dává složitost n^2.
Que – 1. Který algoritmus třídění zabere nejméně času, když jsou všechny prvky vstupního pole shodné? Uvažujte typické implementace třídicích algoritmů.
(A) Vsunuté třídění
(B) Řazení na hromadě
(C) Slučovací třídění
(D) Selekční třídění
Řešení: Jak bylo řečeno, insertion sort bude mít složitost n, pokud je vstupní pole již setříděno.
Kvůli – 2. Uvažujme algoritmus Quicksort. Předpokládejme, že existuje procedura pro nalezení pivotního prvku, která rozdělí seznam na dva dílčí seznamy, z nichž každý obsahuje alespoň pětinu prvků. Nechť T(n) je počet porovnání potřebných k setřídění n prvků. Pak (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Řešení: Složitost rychlého třídění lze zapsat takto:
T(n) = T(k) + T(n-k-1) + cn
Jak je uvedeno v otázce, jeden seznam obsahuje 1/5 všech prvků. Proto jiný seznam bude obsahovat 4/5 celkových prvků. Dosazením hodnot dostaneme:
T(n) = T(n/5) + T(4n/5) + cn, což odpovídá možnosti (B).
Tabulka porovnání časové a prostorové složitosti :
| Třídicí algoritmus | Časová složitost | Prostorová složitost | ||
|---|---|---|---|---|
| Nejlepší případ | Průměrná hodnota Případ | Nejhorší případ | Nejhorší případ | |
| Bublinové třídění | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Výběrové třídění | Ω(N2) | Θ(N2) | O(N2) | O(1) |
| Vložné třídění | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Merge Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) |
| Heap Sort | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) |
| Rychlé třídění | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) |
| Radixové třídění | Ω(N k) | Θ(N k) | O(N k) | O(N + k) |
| Count Sort | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
| Bucket Sort | Ω(N + k) | Θ(N + k) | O(N2) | O(N) |
