QuickSelect: Der mit Codebeispielen erläuterte Schnellauswahlalgorithmus

Was ist QuickSelect?

QuickSelect ist ein Auswahlalgorithmus, um das K-te kleinste Element in einer unsortierten Liste zu finden.

Der Algorithmus erklärt

Nachdem der Pivot gefunden wurde (eine Position, die die Liste in zwei Teile unterteilt: Jedes Element links ist kleiner als der Pivot und jedes Element rechts ist größer als der Pivot), wird der Algorithmus nur für den Teil wiederholt, der das k-te enthält kleinstes Element.

Wenn der Index des partitionierten Elements (Pivot) größer als k ist, wird der Algorithmus für den linken Teil wiederholt. Wenn der Index (Pivot) mit k identisch ist, haben wir das k-te kleinste Element gefunden und es wird zurückgegeben. Wenn der Index kleiner als k ist, wiederholt sich der Algorithmus für den richtigen Teil.

Auswahl 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 

Partition

Die Partition besteht darin, den Drehpunkt wie oben erwähnt zu finden. (Jedes Element auf der linken Seite ist kleiner als der Pivot und jedes Element auf der rechten Seite ist mehr als der Pivot.) Es gibt zwei Algorithmen zum Ermitteln des Pivots der Partition.

  • Lomuto-Partition
  • Hoare Partition

Lomuto-Partition

Diese Partition wählt einen Pivot aus, der normalerweise das letzte Element im Array ist. Der Algorithmus behält den Index i bei, während er das Array unter Verwendung eines anderen Index j abtastet, so dass die Elemente lo bis i (einschließlich) kleiner oder gleich dem Drehpunkt sind und die Elemente i + 1 bis j-1 (einschließlich) größer als der sind schwenken.

Dieses Schema verschlechtert sich, O(n^2)wenn das Array bereits in Ordnung ist.

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 verwendet zwei Indizes, die an den Enden des zu partitionierenden Arrays beginnen und sich dann aufeinander zu bewegen, bis sie eine Inversion erkennen: ein Elementpaar, eines größer oder gleich dem Pivot, eines kleiner oder gleich dem Pivot sind in der falschen Reihenfolge relativ zueinander.

Die invertierten Elemente werden dann ausgetauscht. Wenn sich die Indizes treffen, stoppt der Algorithmus und gibt den endgültigen Index zurück. Es gibt viele Varianten dieses Algorithmus.

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]