QuickSelect:コード例で説明されているクイック選択アルゴリズム

QuickSelectとは何ですか?

QuickSelectは、ソートされていないリストでK番目に小さい要素を見つけるための選択アルゴリズムです。

アルゴリズムの説明

ピボット(リストを2つの部分に分割する位置:左側のすべての要素がピボットより小さく、右側のすべての要素がピボットより大きい)を見つけた後、アルゴリズムはk番目を含む部分に対してのみ繰り返されます。最小の要素。

パーティション化された要素(ピボット)のインデックスがkより大きい場合、アルゴリズムは左側の部分に対して繰り返されます。インデックス(ピボット)がkと同じである場合、k番目に小さい要素が見つかり、それが返されます。indexがk未満の場合、アルゴリズムは適切な部分に対して繰り返されます。

選択擬似コード

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 

パーティション

パーティションは、上記のようにピボットを見つけることです。(左側のすべての要素はピボットより小さく、右側のすべての要素はピボットより大きくなります)パーティションのピボットを見つけるための2つのアルゴリズムがあります。

  • Lomutoパーティション
  • Hoareパーティション

Lomutoパーティション

このパーティションは、通常、配列の最後の要素であるピボットを選択します。アルゴリズムは、別のインデックスjを使用して配列をスキャンするときにインデックスiを維持し、要素loからi(両端を含む)がピボット以下であり、要素i + 1からj-1(両端を含む)がピボット。

このスキームO(n^2)は、アレイがすでに正常に機能している場合に低下します。

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パーティション

Hoareは、分割されている配列の端から始まり、反転を検出するまで互いに向かって移動する2つのインデックスを使用します。1つはピボット以上、もう1つはピボット以下の要素のペアです。互いに対して間違った順序になっています。

次に、反転された要素が交換されます。インデックスが一致すると、アルゴリズムは停止し、最終的なインデックスを返します。このアルゴリズムには多くのバリエーションがあります。

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]