Ce este QuickSelect?

QuickSelect este un algoritm de selecție pentru a găsi cel mai mic element K dintr-o listă nesortată.

Algoritmul explicat

După găsirea pivotului (o poziție care împarte lista în două părți: fiecare element din stânga este mai mic decât pivotul și fiecare element din dreapta este mai mult decât pivotul) algoritmul se repetă numai pentru partea care conține k-th cel mai mic element.

Dacă indexul elementului partiționat (pivot) este mai mare de k, atunci algoritmul se repetă pentru partea stângă. Dacă indexul (pivotul) este același cu k, atunci am găsit cel de-al treilea cel mai mic element și este returnat. Dacă indexul este mai mic decât k, atunci algoritmul se repetă pentru partea dreaptă.

Selecție 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

Partiție

Partiția constă în găsirea pivotului așa cum s-a menționat mai sus. (Fiecare element din stânga este mai mic decât pivotul și fiecare element din dreapta este mai mult decât pivotul) Există doi algoritmi pentru găsirea pivotului partiției.

  • Lomuto Partition
  • Partiția Hoare

Lomuto Partition

Această partiție alege un pivot care este de obicei ultimul element din matrice. Algoritmul menține indicele i deoarece scanează matricea folosind un alt index j astfel încât elementele de la lo la i (inclusiv) să fie mai mici sau egale cu pivotul, iar elementele i + 1 la j-1 (inclusiv) sunt mai mari decât pivot.

Această schemă se degradează la O(n^2) când matricea este deja în ordine.

ad-banner
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

Partiția Hoare

Hoare folosește doi indici care încep de la capetele matricei partiționate, apoi se deplasează unul către celălalt până când detectează o inversiune: o pereche de elemente, unul mai mare sau egal cu pivotul, unul mai mic sau egal cu pivotul, care sunt în ordinea greșită unul față de celălalt.

Elementele inversate sunt apoi schimbate. Când indicii se întâlnesc, algoritmul se oprește și returnează indexul final. Există multe variante ale acestui algoritm.

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

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]