Quickselect

O(n) avg

Quickselect používá rozdělovací krok z quicksortu, ale po rozdělení pokračuje rekurzí jen do strany, která obsahuje hledanou pozici — tady medián. Díky tomu je v průměru O(n) (oproti O(n log n) na úplné seřazení) a je základem efektivního hledání mediánu a výběru „top-k“.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Rozděl pole kolem pivota jako v quicksortu.
  2. Pivot skončí na své konečné seřazené pozici p.
  3. Když je p hledaný index k, hotovo; jinak pokračuj rekurzí jen do strany s k.
  4. Opakuj, dokud k-tá nejmenší hodnota nesedí na místě.

Pseudokód

1quickselect(a, k):                  # O(n) average2  lo ← 0; hi ← n-13  while lo < hi:4    p ← partition(a, lo, hi)         # pivot lands at p (quicksort step)5    if p = k: break6    if p < k: lo ← p+1               # recurse into one side only7    else: hi ← p-18  return a[k]                         # the k-th smallest