QuickSelect: Pika-algoritmi, joka selitetään koodiesimerkkeillä

Mikä on QuickSelect?

QuickSelect on valintaalgoritmi, jolla löydät K: n pienimmän elementin lajittelemattomasta luettelosta.

Algoritmi selitetty

Löydettyään pivot (sijainti, joka jakaa luettelon kahteen osaan: jokainen elementti vasemmalla on pienempi kuin pivot ja jokainen elementti oikealla on enemmän kuin pivot), algoritmi toistuu vain osalle, joka sisältää k: n pienin elementti.

Jos osioidun elementin (pivot) indeksi on suurempi kuin k, algoritmi toistuu vasemmalle osalle. Jos indeksi (pivot) on sama kuin k, olemme löytäneet k: n pienimmän elementin ja se palautetaan. Jos indeksi on pienempi kuin k, algoritmi toistuu oikean osan kohdalla.

Psudokoodin valinta

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 

Osio

Osio on löytää pivot edellä mainitulla tavalla. (Jokainen vasemmanpuoleinen elementti on pienempi kuin pivot ja jokainen oikealla oleva elementti on enemmän kuin pivot) Osiotapin löytämiselle on kaksi algoritmia.

  • Lomuto-osio
  • Hoare-osio

Lomuto-osio

Tämä osio valitsee pivotin, joka on tyypillisesti matriisin viimeinen elementti. Algoritmi ylläpitää indeksiä i skannatessaan taulukkoa toisella indeksillä j siten, että elementit lo - i (mukaan lukien) ovat pienempiä tai yhtä suuria kuin kääntö, ja elementit i + 1 - j-1 (mukaan lukien) ovat suurempia kuin kääntö.

Tämä järjestelmä hajoaa, O(n^2)kun taulukko on jo kunnossa.

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-osio

Hoare käyttää kahta indeksiä, jotka alkavat jaettavan taulukon päistä ja liikkuvat sitten toisiaan kohti, kunnes havaitsevat inversion: pari elementtiä, yksi suurempi tai yhtä suuri kuin sarana, yksi pienempi tai yhtä suuri kuin sarana, joka ovat väärässä järjestyksessä toistensa suhteen.

Käänteiset elementit vaihdetaan sitten. Kun indeksit kohtaavat, algoritmi pysähtyy ja palauttaa lopullisen indeksin. Tästä algoritmista on monia muunnelmia.

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]