QuickSelect: Quick Select-algoritmen forklaret med kodeeksempler

Hvad er QuickSelect?

QuickSelect er en valgalgoritme til at finde det K-th mindste element på en usorteret liste.

Algoritmen forklaret

Efter at have fundet pivoten (en position, der opdeler listen i to dele: hvert element til venstre er mindre end pivot og hvert element til højre er mere end pivot) algoritmen vender kun tilbage for den del, der indeholder k-th mindste element.

Hvis indekset for det partitionerede element (pivot) er mere end k, gentages algoritmen for den venstre del. Hvis indekset (pivot) er det samme som k, har vi fundet det k-th mindste element, og det returneres. Hvis indekset er mindre end k, gentages algoritmen for den rigtige del.

Valg af 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 

Skillevæg

Partition er at finde drejetappen som nævnt ovenfor. (Hvert element til venstre er mindre end pivot, og hvert element til højre er mere end pivot) Der er to algoritmer til at finde partitionens pivot.

  • Lomuto Partition
  • Hoare Partition

Lomuto Partition

Denne partition vælger en pivot, der typisk er det sidste element i arrayet. Algoritmen opretholder indeks i, da det scanner arrayet ved hjælp af et andet indeks j, således at elementerne lo gennem i (inklusive) er mindre end eller lig med drejetappen, og elementerne i + 1 til j-1 (inklusive) er større end omdrejningspunkt.

Denne ordning nedbrydes, O(n^2)når arrayet allerede er i orden.

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 Partition

Hoare bruger to indekser, der starter ved enderne af det array, der er opdelt, og bevæger sig derefter mod hinanden, indtil de registrerer en inversion: et par elementer, en større end eller lig med drejetappen, en mindre end eller lig med drejetappen, som er i den forkerte rækkefølge i forhold til hinanden.

De omvendte elementer byttes derefter. Når indekserne mødes, stopper algoritmen og returnerer det endelige indeks. Der er mange varianter af denne algoritme.

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]