クイックソート (逆順で表示) は次のように機能します。配列があるとします：
[1, 4, 5, 2, 3]
抽象的なクイックソートは、基本的に、左側と右側の両方から配列の中央に向かってスライドすることによって機能します。内側にスライドすると、大きなものは右に移動し、小さなものは左に移動するように項目を入れ替えます。最終的には、すべての小さなものが左側にあり、すべての大きなものが右側にある配列が必要です。
このプロセスの結果として、1 つの要素が正しい位置に配置されることも保証されます (左側の要素はすべて小さくなり、右側の要素はすべて大きくなるため、正しい位置に配置する必要があります)。その値は と呼ばれますpivot。クイックソートの最初のステップは、ピボットが正しい場所にあることを確認することです。
これを行う方法は、ランダムな要素を選択することです。これは、pivot正しい場所に配置したいアイテムです。この単純な例では、最後の数字のみを使用します(3)。はpivot当社比較値です。
/comparison 値を選択したら、一番左の要素と一番右のpivot要素を監視します。これらをおよび と呼びます。ジョブは、配列の中央に向かってスライドし、. ポインターも同じことを行いますが、より小さい値を探して内側にスライドします。コード内:(1)(3)left-pointerright-pointerleft-pointerspivotrightpivot
while (true) {
while (array[++left] < pivot);
while (array[--right] > pivot) if (left == right) break;
if (left >= right) break; // If the pointers meet then exit the loop
swap(array[left], array[right]); // Swap the values otherwise.
}
上記の例では、left-pointerヒット(4)がピボット要素よりも高いことを認識し、動きを停止します。右のピボットは右側から同じことを行いますが、よりも低い(2)ため、ヒットすると停止します。両側が停止すると、スワップを行うため、最終的には次のようになります。pivot
[1, 2, 5, 4, 3]
sorted に近づいていることに注意してください。両方のポインターが同じ要素を指すか交差するまで、両方のポインターを内側に移動し続けます。(3)その場合、ピボット要素を が指している任意のポイントに置き換えるという最後のステップを行いますleft/right-pointers。この場合、(5)両方とも真ん中で停止するためです。次に、次のように交換します。
[1, 2, 3, 4, 5]
(Notice that we swap the original pivot (3) with the value pointed to by both sides (5))
このプロセス全体をパーティションと呼びます。コードでは次のようになります。
int partition(int *array, int lBound, int rBound) {
int pivot = array[rBound]; // Use the last element as a pivot
int left = lBound - 1; // Point to one before the first element
int right = rBound; // Point to the last element;
// We'll break out of the loop explicity
while (true) {
while (array[++left] < pivot);
while (array[--right] > pivot) if (left == right) break;
if (left >= right) break; // If the pointers meet then exit the loop
swap(array[left], array[right]); // Swap the pointers otherwise.
}
swap(array[left], array[rBound]); // Move the pivot item into its correct place
return left; // The left element is now in the right place
}
この例では、分割ステップによって配列が完全にソートされていますが、通常、それは分割ステップのポイントではないことに注意してください。分割ステップのポイントは、1 つの要素を正しい場所に配置し、その要素の左側のすべてが少なくなり、右側のすべてが多くなるようにすることです。つまり、pivot値を正しい位置に移動し、ピボットの左側のすべてがそれよりも小さく、右側のすべてが大きいことを保証します。したがって、この例では配列は完全にソートされていますが、一般に、 1 つのアイテムと1つのアイテムのみが保証されます。アイテムのみが正しい位置にあります (左右のすべてがそれぞれ大きく/小さくなっています)。これが、partition上記のメソッドが を返す理由です。これは、この1 つの要素が正しい場所にある (そして配列が正しく分割されている)leftことを呼び出し元の関数に伝えるためです。
それは、次のような配列から始める場合です。
[1, 7, 5, 4, 2, 9, 3]
次に、分割ステップは次のようなものを返します。
[1, 3, 2, [4], 7, 5, 9]
[4] は正しい場所にあることが保証されている唯一の値ですが、左側のすべては [4] よりも小さく、右側のすべては大きくなっています (ただし、必ずしもソートされているわけではありません!) 。
2 番目のステップは、このステップを再帰的に実行することです。つまり、1 つの要素を正しい場所に配置できれば、最終的にはすべてのアイテムを正しい場所に配置できるはずです。それがquicksort機能です。コード内:
int *quicksort(int *array, int lBound, int rBound) {
if (lBound >= rBound) return array; // If the array is size 1 or less - return.
int pivot = partition(array, lBound, rBound); // Split the array in two.
quicksort(array, lBound, pivot - 1); // Sort the left size. (Recursive)
quicksort(array, pivot + 1, rBound); // Sort the right side. (Recursive)
return array;
}
最初のステップは、配列の辺が少なくとも 2 であることを確認することです。それよりも小さいものを処理しても意味がないため、条件が満たされない場合は戻ります。次のステップは、上記のプロセスに従って配列を分割するパーティション関数を呼び出すことです。配列に正しい位置にある 1 つの要素があることがわかったら、もう一度クイックソートを呼び出しますが、今度はピボットの左側で、次にピボットの右側でもう一度呼び出します。ピボットは含まれていないことに注意してください。これは、パーティションがピボットを正しい場所に配置することが保証されているためです。
再帰的に呼び出し続けるとquicksort、最終的に配列を半分にし、サイズ 1 の配列を取得するまで分割します (定義により、既にソートされています)。したがって、配列全体が（所定の位置で）ソートされるまで、分割してから半分に分割し、分割し、半分に分割します。これにより、O(n lg(n))時間の並べ替えができます。涼しい！
以下は、その使用の簡単な例です。
int main() {
int array [] {1, 0, 2, 9, 3, 8, 4, 7, 5, 6};
quicksort(array, 0, 9); // Sort from zero to 9.
// Display the results
for (int index = 0; index != 10; ++index) {
cout << array[index] << endl;
}
return 0;
}
優れた視覚的なデモンストレーションがここにあります: http://www.youtube.com/watch?v=Z5nSXTnD1I4