Quick Sort

Princip

  1. Zvolíme 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.

Pseudokód

Vstup: pole P[1 … n]
Výstup: vzestupně seřazené pole P
Algoritmus QuickSort(X=x1, … , xn)
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
Rekurzivně seřaď části L a P:
    L:= QuickSort(L)
    P:= QuickSort(P)
Spoj části za sebe: Y:=L, S, P
Vrať Y

 

Složitost

Pokud za pivoty volím emediány nebo alespoň skoromediány, pak:
Střední hodnota časové složitosti QuickSortu s rovnoměrně náhodnou volbou pivota je O(nlogn).

Důkaz
  1. Velikosti podproblémů klesají exponenciálně: na i-té hladině SRV je velikost většího z L, P je nejvýše (3/4)i·n.
  2. SRV má tudíž hloubku O(log4/3n) = O(logn).
  3. V součtu přes všechny hladiny proto časová složitost činí O(nlogn).

V nejlepším případě: t(n) = 2t(n/2) + Θ(n)

V průměrném případě: t(n) =t(9n/10) + t(n/10) + Θ(n)

Implementace v C

void qsort(int v[], int left, int right) {
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)          /* do nothing if array contains */
        return;                 /* fewer than two elements */

    swap(v, left, (left + right)/2); /* move partition elem */
    last = left;                /* to v[0] */

    for (i = left + 1; i <= right; i++) /* partition */
        if (v[i] < v[left])
            swap(v, ++last, i);

    swap(v, left, last);        /* restore partition  elem */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

Celý kód ke stažení zde.

Související