Mi a QuickSelect?
A QuickSelect egy választási algoritmus a K-edik legkisebb elem megkeresésére egy nem rendezett listában.
Az algoritmus magyarázata
Miután megtalálta a pivot (egy olyan pozíció, amely két részre osztja a listát: a bal oldalon minden elem kevesebb, mint a pivot, a jobb oldalon pedig minden elem nagyobb, mint a pivot), az algoritmus csak annak a résznek felel meg, amely tartalmazza a k-t legkisebb elem.
Ha a particionált elem (pivot) indexe nagyobb, mint k, akkor az algoritmus megismétlődik a bal résznél. Ha az index (pivot) megegyezik k-vel, akkor megtaláltuk a k-edik legkisebb elemet, és visszaadjuk. Ha az index kisebb, mint k, akkor az algoritmus a jobb résznél megismétlődik.
Válogatás 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 Partíció
A partíciónak meg kell találnia a forgásirányt a fentiek szerint. (A bal oldalon minden elem kevesebb, mint a pivot, és a jobb oldalon minden elem több, mint a pivot) A partíció pivotjának megtalálásához két algoritmus létezik.
- Lomuto partíció
- Hoare partíció
Lomuto partíció
Ez a partíció olyan pivot választ, amely általában a tömb utolsó eleme. Az algoritmus fenntartja az i indexet, miközben egy másik j index segítségével beolvassa a tömböt, így a lo-i (beleértve) elemek kisebbek vagy egyenlőek a forgási ponttal, és az i + 1 - j-1 (beleértve) elemek nagyobbak, mint a forgatható.
Ez a séma akkor degradálódik, O(n^2)amikor a tömb már rendben van.
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 partíció
Hoare két indexet használ, amelyek a particionálandó tömb végéből indulnak, majd egymás felé mozognak, amíg észlelnek egy inverziót: egy pár elemet, amelyek egyek vagy nagyobbak a forgáspontnál, egyek kisebbek vagy egyenlőek a forgáspontoknál, amelyek rossz sorrendben vannak egymáshoz képest.
Ezután a megfordított elemeket felcseréljük. Amikor az indexek találkoznak, az algoritmus leáll és visszaadja a végső indexet. Ennek az algoritmusnak számos változata létezik.
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]