QuickSelect: Kiirvaliku algoritm, mida selgitatakse koodinäidetega

Mis on QuickSelect?

QuickSelect on valimisalgoritm sorteerimata loendis K-nda väikseima elemendi leidmiseks.

Algoritm selgitatud

Pärast pivoti leidmist (positsioon, mis jagab loendi kaheks osaks: iga vasakpoolne element on väiksem kui pivot ja iga paremal olev element on rohkem kui pivot), kordub algoritm ainult selle osa jaoks, mis sisaldab k-d väikseim element.

Kui jaotatud elemendi indeks (pivot) on suurem kui k, siis algoritm kordub vasakpoolse osa puhul. Kui indeks (pöördetapp) on sama mis k, siis oleme leidnud k-nda väikseima elemendi ja see tagastatakse. Kui indeks on väiksem kui k, kordub algoritm parempoolses osas.

Valik Psudokood

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 

Jaotus

Jaotus on ülaltoodud pöördtapi leidmine. (Iga vasakpoolne element on väiksem kui pöördetapp ja iga paremal olev element on rohkem kui pöördetapp) Jaotuse pöördliigi leidmiseks on kaks algoritmi.

  • Lomuto partitsioon
  • Hoare vahesein

Lomuto partitsioon

See sektsioon valib pöördetapi, mis on tavaliselt massiivi viimane element. Algoritm säilitab indeksi i, kuna see skaneerib massiivi teise indeksi j abil nii, et elemendid lo kuni i (kaasa arvatud) on pöördega väiksemad või võrdsed ning elemendid i + 1 kuni j-1 (kaasa arvatud) on suuremad kui pöördetapp.

See skeem laguneb O(n^2)siis, kui massiiv on juba korras.

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 vahesein

Hoare kasutab kahte indeksit, mis algavad jaotatava massiivi otsadest ja liiguvad seejärel üksteise suunas, kuni tuvastavad inversiooni: paar elementi, üks suurem või võrdne pöördteljega, üks väiksem või võrdne pöördliigendiga, mis on üksteise suhtes vales järjekorras.

Seejärel vahetatakse ümberpööratud elemendid. Kui indeksid kokku saavad, peatub algoritm ja tagastab lõpliku indeksi. Selle algoritmi variante on palju.

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]