Skip to content

9.1 Quicksort

QuickSort je řadící algoritmus založený na podobné myšlence jako QuickSelect:

  1. Vybereme pivota a rozdělíme vstup na levou \(L\) (prvky menší než pivot), střední \(S\) (prvky rovné pivotu) a pravou \(P\) část (prvky větší než pivot).
  2. V seřazené posloupnosti budou vystupovat nejdříve prvky z \(L\), pak ty z \(S\) a nakonec prvky z \(P\)
  3. Rekurzivně tedy seřadíme levou \(L\) a pravou \(P\) část (střední \(S\) je sama od sebe seřazená).
  4. Výsledná posloupnost vznikne spojením \(L\), \(S\) a \(P\) za sebou

Algoritmus 9.1 (Quicksort)

Algoritmus Quicksort

QuickSort(X = x1, . . . , xn)
1
2
3
4
5
6
7
8
9
Pokud n ≤ 1: vrať X a skonči
p := některý z prvků x1, . . . , xn //pivot
L := prvky v X, které jsou menší než p
S := prvky v X, které jsou rovny p
P := prvky v X, které jsou větší než p
L := QuickSort(L) //rekurzivně seřaď část L
P := QuickSort(P) //rekurzivně seřaď část P
Y := L, S, P //spoj části za sebe
Vrať Y

Strom rekurzivních volání (SRV) QuickSortu

  1. V kořeni SRV máme celou posloupnost \(n\) prvků, na první hladině její levou a pravou část, na druhé hladině levé a pravé části těchto částí, a tak dále, až v listech triviální posloupnosti délky \(1\)
  2. Součet velikostí všech podproblémů v libovolné hladině SRV je tedy nejvýše \(n\)
  3. Rozkládání vstupu i spojování částí jsou operace v lineárním čase.
  4. V každém vrcholu SRV stráví algoritmus čas úměrný velikosti příslušného podproblému.
  5. Na jedné hladině SRV proto algoritmus stráví čas \(O(n)\)