データ構造とアルゴリズム-クイックソート
クイックソートは非常に効率的なソートアルゴリズムであり、データの配列をより小さな配列に分割することに基づいています。大きな配列は2つの配列に分割され、そのうちの1つは指定された値よりも小さい値、たとえばピボットを保持します。これに基づいて分割が行われ、もう1つの配列はピボット値より大きい値を保持します。
クイックソートは配列を分割し、それ自体を2回再帰的に呼び出して、結果の2つのサブ配列をソートします。このアルゴリズムは、平均および最悪の場合の複雑さがそれぞれO（n 2）であるため、大規模なデータセットに対して非常に効率的です。
クイックソートでのパーティション
次のアニメーション表現は、配列内のピボット値を見つける方法を説明しています。
ピボット値は、リストを2つの部分に分割します。そして再帰的に、すべてのリストに1つの要素のみが含まれるまで、各サブリストのピボットを見つけます。
クイックソートピボットアルゴリズム
クイックソートでのパーティショニングの理解に基づいて、次のようなアルゴリズムを作成してみましょう。
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivotクイックソートピボット擬似コード
上記のアルゴリズムの擬似コードは、次のように導出できます。
function partitionFunc(left, right, pivot)
leftPointer = left
rightPointer = right - 1
while True do
while A[++leftPointer] < pivot do
//do-nothing
end while
while rightPointer > 0 && A[--rightPointer] > pivot do
//do-nothing
end while
if leftPointer >= rightPointer
break
else
swap leftPointer,rightPointer
end if
end while
swap leftPointer,right
return leftPointer
end functionクイックソートアルゴリズム
ピボットアルゴリズムを再帰的に使用すると、可能なパーティションが小さくなります。次に、各パーティションはクイックソートのために処理されます。クイックソートの再帰的アルゴリズムを次のように定義します-
Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursivelyクイックソート擬似コード
さらに詳しく知るために、クイックソートアルゴリズムの擬似コードを見てみましょう-
procedure quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedureCプログラミング言語でのクイックソートの実装については、ここをクリックしてください。