QuickSelect: Algoritmus rýchleho výberu vysvetlený príkladmi kódu

Čo je to QuickSelect?

QuickSelect je výberový algoritmus na vyhľadanie K-tého najmenšieho prvku v netriedenom zozname.

Vysvetlený algoritmus

Po nájdení otočného bodu (pozícia, ktorá rozdeľuje zoznam na dve časti: každý prvok vľavo je menší ako otočný čap a každý prvok vpravo je viac ako otočný čap) sa algoritmus opakuje iba pre časť, ktorá obsahuje k-tú najmenší prvok.

Ak je index rozdeleného prvku (pivot) väčší ako k, potom sa algoritmus opakuje pre ľavú časť. Ak je index (pivot) rovnaký ako k, potom sme našli k-tý najmenší prvok a vráti sa. Ak je index menší ako k, potom sa algoritmus opakuje pre pravú časť.

Výber psudokódu

Input : List, left is first position of list, right is last position of list and k is k-th smallest element. Output : A new list is partitioned. quickSelect(list, left, right, k) if left = right return list[left] // Select a pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1 

Priečka

Oblasť spočíva v nájdení otočného bodu, ako je uvedené vyššie. (Každý prvok vľavo je menší ako otočný čap a každý prvok vpravo je viac ako otočný čap) Existujú dva algoritmy na vyhľadanie otočného prvku oddielu.

  • Lomuto oddiel
  • Hoare Partition

Lomuto oddiel

Táto oblasť vyberá pivot, ktorý je zvyčajne posledným prvkom v poli. Algoritmus udržuje index i pri skenovaní poľa pomocou iného indexu j tak, že prvky lo až i (vrátane) sú menšie alebo rovnaké ako otočný bod a prvky i + 1 až j-1 (vrátane) sú väčšie ako pivot.

Táto schéma sa degraduje, O(n^2)keď je pole už v poriadku.

algorithm Lomuto(A, lo, hi) is pivot := A[hi] i := lo for j := lo to hi - 1 do if A[j] < pivot then if i != j then swap A[i] with A[j] i := i + 1 swap A[i] with A[hi] return i 

Hoare Partition

Hoare používa dva indexy, ktoré začínajú na koncoch rozdeleného poľa, a potom sa pohybujú smerom k sebe, kým nezistia inverziu: pár prvkov, jeden väčší alebo rovný otočnému bodu, druhý menší alebo rovný otočnému bodu, ktorý sú navzájom v nesprávnom poradí.

Obrátené prvky sa potom zamenia. Keď sa indexy stretnú, algoritmus sa zastaví a vráti konečný index. Existuje veľa variantov tohto algoritmu.

algorithm Hoare(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do i := i + 1 while A[i]  pivot if i >= j then return j swap A[i] with A[j]