Pojmy

• stabilní algoritmus - zachovává vzájemné pořadí pro položky se stejným klíčem (byla položka a před b a mají stejné klíče, musí být i po seřazení a před b)
• extrasekvenční prostorová složitost - prostorová složitost bez paměti obsazenou vstupní posloupností
• in situ - algoritmy s konstantní extrasekvenční prostorovou složitostí

Stabilní algoritmy a algoritmy

• prvky množiny $K$ mohou být strukturované
• řazení podle klíče
• řazení se nazývá stabilní právě když zachovává vzájemné pořadí položek se stejným klíčem

• prostorová složitost algoritmů řazení je v $\Omega(n)$, protože samotná vstupní posloupnost má délku $n$
• pro přesnější charakterizaci prostorové složitosti jednotlivých algoritmů uvažujeme tzv. extrasekvenční prostorová složitost, do které nezapočítáváme paměť obsazenou vstupní posloupností
• algoritmy, jejichž extrasekveční složitost je konstantní, se nazývají in situ (in place)

Způsob	Název	Časová složitost	Prostorová složitost	Stabilita
vkládáním	Insertion sort		in situ	stabilní
výběrem	Selection sort		in situ	nestabilní
sléváním	Merge sort	asymptoticky časově optimální	není in situ	stabilní
haldou	Heap sort	asymptoticky časově optimální	in situ	nestabilní
rozdělováním	Quicksort	není časově optimální	depends	velmi dobrý v praxi

Merge sort

• rozděl posloupnost na dvě stejně velké podposloupnosti
• seřaď obě podposloupnosti (rekurzivně)
• spoj dvě seřazené podposloupnosti spoj do jedné seřazené podposloupnosti
  • procedura Merge
  • bere prvky dvou podposloupností zleva a porovná
  • menší prvek vkládá zprava

Složitost procedury Merge

• kopírování prvků pole $A$ do pole aux má složitost lineární vzhledem k počtu prvků v $A$
• slévání má taky složitost lineární vzhledem k počtu prvků
• zbyle instrukce mají konstantní složitost
• složitost procedury Merge je lineární vzhledem k délce vstupu

Algoritmus MergeSort

• využívá Merge
• pro seřazení celé posloupnosti volání MergeSort(A,0,n-1)

function MergeSort(A,left,right)
  if left < right then
    mid = (left + right)//2
    MergeSort(A,left,mid)
    MergeSort(A,mid+1,righ)
    Merge(A,left,mid,right)

Složitost

• rozdělení znamená výpočet indexu, proto má konstantní složitost
• rekurzivně zpracujeme dvě posloupnosti velikosti $\lfloor n/2 \rfloor$ a $\lceil n/2 \rceil$; časová složitost je $T(\lfloor n/2 \rfloor)$ resp. $T(\lceil n/2 \rceil)$
• složitost procedury Merge je lineární
• pro vhodné konstanty $c$ a $d$ můžeme složitost vyjádřit rovnicí $$T(n) = \begin{cases} c & \text{pro } n = 1 \ 2 T(n/2) + d \cdot n & \text{jinak} \ \end{cases}$$
• složitost algoritmu MergeSort je v třídě $O(n \log n)$

Quicksort

• rozděl posloupnost na dvě posloupnosti tak, aby všechny prvky v první podposloupnosti byly menší nebo nejvýše rovné než prvky v druhé podposloupnosti
• seřaď obě podposloupnosti (rekurzivně)
• spoj dvě seřazené podposloupnosti zřetězením

Principy

• hlavní část algoritmu je rozdělování posloupnosti do dvou posloupností požadovaných vlastností
• při rozdělování využíváme pivota
• každý prvek posloupnosti porovnáváme s pivotem
• podposloupnosti prvků menších/větších než pivot

In situ

• 3 části - <= pivot; > pivot; nezpracované
• pivot je na konci
• jestli je prvek v nezpracované části > pivot, tak j <- j+1
• jestli je první prvek v nezpracované části <= pivot, swap(a[i],a[j]), i <- i+1, j <- j+1

Složitost

• V nejhoším případě:
  • $T(n) = T(n-1) + T(0) + \Theta (n) = T(n-1) + \Theta(n)$
  • $\color{red} T(n) \in \Theta (n^2)$
• půměrné složitost:
  • $\color{green} T(n) \in \Theta(n \log n)$

Hoare Partition

• pivot je první prvek posloupnosti
• postupujeme od obou konců posloupnosti až do chvíle, než jsou detekovány prvky, které jsou v opačném pořadí vůči pivotu; prvky si vymění pozici
• funkce vrátí index $m$ takový, že všechny prvky v $A[left…m]$ jsou menší anebo rovny prvkům v $A[m+1…right]$