QuickSelect: Algoritam brzog odabira objašnjen s primjerima koda

Što je QuickSelect?

QuickSelect je algoritam za odabir za pronalaženje K-tog najmanjeg elementa na nesortiranom popisu.

Objašnjeni algoritam

Nakon pronalaska stožera (položaj koji dijeli popis na dva dijela: svaki je element lijevo manji od pivota, a svaki element s desne strane veći je od pivota) algoritam se ponavlja samo za dio koji sadrži k-th najmanji element.

Ako je indeks particioniranog elementa (pivot) veći od k, tada se algoritam ponavlja za lijevi dio. Ako je indeks (pivot) jednak k, tada smo pronašli k-ti najmanji element i on se vraća. Ako je indeks manji od k, tada se algoritam ponavlja za desni dio.

Izbor Psudocode

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 

Pregrada

Particija je pronaći stožer kao što je gore spomenuto. (Svaki element s lijeve strane manji je od stožera, a svaki element s desne strane više od pivota) Postoje dva algoritma za pronalaženje stožera particije.

  • Lomutska pregrada
  • Pregrada Hoare

Lomutska pregrada

Ova particija bira osovinu koja je obično posljednji element u nizu. Algoritam održava indeks i dok skenira niz koristeći drugi indeks j takav da su elementi od lo do i (uključujući) manji ili jednaki osovini, a elementi i + 1 do j-1 (uključujući) veći su od stožer.

Ova se shema razgrađuje do O(n^2)trenutka kada je niz već u redu.

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 

Pregrada Hoare

Hoare koristi dva indeksa koji započinju na krajevima niza koji se dijeli, a zatim se kreću jedni prema drugima dok ne otkriju inverziju: par elemenata, jedan veći ili jednak pivotu, jedan manji ili jednak pivotu, koji su u pogrešnom redoslijedu jedni prema drugima.

Obrnuti elementi se zatim zamijene. Kad se indeksi sretnu, algoritam se zaustavlja i vraća konačni indeks. Postoje mnoge inačice ovog algoritma.

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]