10.5 Složitost třídících algoritmů

Jak složité je uspořádat zadanou \(n\)-tici objektů? Abychom na tuto otázku mohli odpovědět, tak si musíme ujasnit co přesně myslíme pod pojmem uspořádat, tj. pod symbolem \(\leq\) a jak měřit složitost.

• Vstup: množina \(\{x_1, \ldots, x_n\}\) a úplné uspořádání \(\leq\) mezi jejími prvky. Velikostí vstupu rozumíme jednoduše počet prvků vstupu.
• Výstup: uspořádaná \(n\)-tice \((x_{k_1},\ldots,x_{k_n})\), kde \((k_1,\ldots,k_n)\) je permutace množiny \(\{1,\ldots,n\}\) a \(x_{k_1} \leq \cdots \leq x_{k_n}\).
• Elementární operace: porovnání dvou prvků.

10.5.1 Uspořádání

Intuitivně si pod „uspořádáním“ představujeme vztah mezi objekty nějaké množiny. Formálně se jedná o relaci⁴¹.

Jinak řečeno, zkoumaný vztah mezi objekty množiny \(M\) modelujeme udáním množiny \(\mathcal{R} \subset M \times M\) takové, že \((a,b)\) do \(\mathcal{R}\) patří, právě když \(a\) a \(b\) jsou v požadovaném vztahu. Je-li \(\mathcal{R}\) relace na množině \(M\) a \((a,b) \in \mathcal{R}\) pak často zkráceně píšeme \(a\mathcal{R}b\).

Relaci \(\mathcal{R}\), jež je uspořádáním, většinou značíme symbolem \(\leq\).

10.5.2 Bublinkový algoritmus (Bubble sort)

Pro připomenutí uvádíme kompletní algoritmus, zřejmě čtenáři známý z předmětu BI-PA1.

procedure bubbleSort(A : array of length n)
  for k in n-1 to 1 do
    sorted = true
    for i in 1 to k do
      if A[i] > A[i+1] then
        swap( A[i], A[i+1] )
        sorted = false
      end if
    end for
    if sorted then return A
  end for
  return A
end procedure

Celkový počet porovnání může být nejhůře (pokud je na vstupu seznam v přesně opačném pořadí) \begin{equation*} (n-1) + (n-2) + \cdots + 2 + 1 = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}.\end{equation*} Pokud je na vstupu již setříděný seznam, pak algoritmus provede \((n-1)\) porovnání (nejlepší varianta). Označíme-li počet porovnání při konkrétním vstupu o velikosti \(n\) jako \(T_n\), můžeme tedy shrnout, že pro složitost Bubble sort platí \begin{equation*} T_n = \mathcal{O}(n^2).\end{equation*}

10.5.3 Quick sort

Nechť je opět dán vstup \(\{x_1,\, x_2,\, \ldots, x_n \}\).

1. Vyber náhodně prvek ze seznamu (nazývaný pivot).
2. Prvky ze seznamu menší než pivot, dej do jednoho podseznamu a prvky větší do druhého podseznamu.
3. Dva kratší seznamy uspořádej podle velikosti.
4. Spoj uspořádaný první seznam, za něj dej pivota a připoj uspořádaný druhý seznam.

Pokud je pivot \(r\)-tým prvkem seznamu (co do velikosti), pak \begin{equation*} T_n = n - 1 + T_{r-1} + T_{n-r}, \quad \text{kde klademe} \ T_0 = T_1 = 0.\end{equation*} Sečtením těchto vztahů pro \(r=1,\, 2,\, \ldots, \, n\): \begin{equation*} \sum_{r=1}^n T_n = \sum_{r=1}^n (n-1) + \sum_{r=1}^n \big( T_{r-1} + T_{n-r} \big) \quad \Longrightarrow \quad n T_n = n(n-1) + 2 \sum_{r=1}^{n-1} T_r.\end{equation*} Poslední rovnost vyjádřeme pro \(k\) a pro \(k-1\) a oba vztahy odečtěme (zbavíme se tím součtu vpravo): \begin{equation*} \begin{aligned} k T_k &= k(k-1) + 2 \sum_{r=1}^{k-1} T_r, \\ (k-1) T_{k-1} &= (k-1)(k-2) + 2 \sum_{r=1}^{k-2} T_r, \\ \text{odečtením:} \ kT_k - (k-1) T_{k-1} &= k(k-1) - (k-1)(k-2) + 2 T_{k-1}. \end{aligned}\end{equation*}

Odvodili jsme tedy vztah \begin{equation*} k T_k - (k+1) T_{k-1} = 2k - 2.\end{equation*} Vydělením číslem \(k(k+1)\) dostáváme \begin{equation*} \frac{T_k}{k+1} - \frac{T_{k-1}}{k} = \frac{2k-2}{k(k+1)}.\end{equation*} Konečně, sečtením těchto rovností pro \(k=1,\, 2, \ldots, n\) \begin{equation*} \begin{aligned} \frac{T_n}{n+1} &= 2 \sum_{k=1}^n \frac{k-1}{k+1} \cdot \frac{1}{k} \leq 2 \sum_{k=1}^n \frac{1}{k} \leq \\ &\leq 2 \bigg( 1 + \int_1^n \frac{1}{x}\,\mathrm{d} x \bigg) = 2 \big( 1 + \ln(n) \big). \end{aligned}\end{equation*} Uzavíráme \begin{equation*} T_n = \mathcal{O}\big( n\, \ln(n) \big).\end{equation*}