クイックソート
名前の通り早くソートすることが可能なソートアルゴリズムです。
特に要素が長い時に効果を発揮します。
自分もバブルソートや挿入ソートと比べてその速さに驚きました。
では、内容を見ていきたいと思います。
まず、以下の数列データがあるとします。
5 14 10 15 13 4 2 7 19 12
要素数は10、でランダムに並んでいます。
これをクイックソートを使用して、昇順にソートしていきたいと思います。
まず、この10個の要素の中からひとつの要素を選びます。
ここでは、要素数の中間の値であるものを選びたいと思います。
コードにすると、
(要素の開始位置 + 要素の終了位置) / 2
つまり、
(0 + 9) / 2 = 4
4番目の要素が中間値となります。
つまり、13です。
そして、この13を基準値にしてデータ数列をソートしていきます。
ちなみに基準となる数字つまり軸となるものをピボットと呼びます。
このピボットを赤数字で示します。
5 14 10 15 13 4 2 7 19 12
次は、このピボットを昇順にソートした時にくる位置に挿入します。
その為に以下の方法を使います。
データ数列の先頭からピボット以上のデータを探し、
またデータ数列の末尾からピボット以下のデータを探して、その値が見つかった場合に、
その値同士を交換していきます。
そして、先頭と末尾の捜査がぶつかるまでこの操作を続けます。
では、先頭から始める捜査を緑数字で、末尾から始める捜査を青数字で表します。
まずは、先頭から始める捜査に関して見ていきます。
5 14 10 15 13 4 2 7 19 12
5は13以上ではないので、次に進めます。
5 14 10 15 13 4 2 7 19 12
14は13以上なので14は交換すべき要素となります。
次は、末尾から捜査します。
5 14 10 15 13 4 2 7 19 12
12は13以下なので、12は交換すべき要素となります。
それでは交換しましょう。
5 12 10 15 13 4 2 7 19 14
要素が交差するまで作業を続けるので、また、先端から捜査していきます。
5 12 10 15 13 4 2 7 19 14
10は13以下ですので、次の要素の見ていきます。
この作業を続けていくわけです。
5 12 10 15 13 4 2 7 19 14
15は13以上ですので、交換要素がきまりました。
次は末尾から捜査します。
5 12 10 15 13 4 2 7 19 14
5 12 10 15 13 4 2 7 19 14
5 12 10 7 13 4 2 15 19 14
末端から検索して7に行き着きました。
そして、先頭要素と末尾要素を交換しました。
さらに続けます。
5 12 10 7 13 4 2 15 19 14
ピボットである13が交換要素となりました。
では末尾を捜査しましょう。
5 12 10 7 13 4 2 15 19 14
5 12 10 7 13 4 2 15 19 14
5 12 10 7 2 4 13 15 19 14
末尾から捜査した2と13を交換しました。
では、先頭から捜査します。
5 12 10 7 2 4 13 15 19 14
5 12 10 7 2 4 13 15 19 14
先頭からの要素を進めて、13が交換すべき要素となりますが、先頭と末尾が交差してしまったので、ここでの作業は終わりです。
次はピボット13を中心にして、左のデータ数列と右のデータ数列を分けて、
上記でやった作業を行います。
この作業を続けて、整列すべきデータ数列が1要素になるまで、
行えば昇順にソートされます。
つまり、
5 12 10 7 2 4 13 15 19 14
ピボットより左のデータ数列とピボットより右のデータ数列に対してそれぞれ別に、
ピボットを決め、上記で行ったソートを行い、ソートが完了したらそのデータ数列のピボットを基に、
ソートを行う。
これを繰り返して、整列すべきデーター数列の要素が1になったらソートの終了です。
では、ピボット13の右側のデータ数列について見ていきます。
15 19 14
ピボットを決める条件はデーター数列の真ん中の値ですから、
(0 + 2) / 2 = 1
1番目の要素を基準値にするので、19がピボットとなります。
では、左側から捜査していきます。
15 19 14
15 19 14
捜査していった結果ピボット自身が交換対象となりました。
では、末端から捜査しましょう。
15 19 14
15 19 14
15 14 19
15 14 19
14と19を交換しました。
その後交差するので、ここでのソートは終了です。
次に、ピボットである19の左右を見ますが、左のデータ数列のみで、
右のデータ数列は要素がないので終了です。
では、左のデータ数列を見ていきましょう。
その後交差するので、ここでのソートは終了です。
次に、ピボットである19の左右を見ますが、左のデータ数列のみで、
右のデータ数列は要素がないので終了です。
では、左のデータ数列を見ていきましょう。
15 14
ピボットは
(0 + 1) / 2 = 0
0番目の要素15がピボットになります。
では左側から捜査します。
15 14
15 14
14 15
ピボットが交換対象となり、14は15以下なので、14と15を交換します。
つぎは、交差するのでここで捜査終了です。
また、ピボットの左側の要素が1となったので、右側のソートも終了します。
ということで、以下のようなデータ数列になります。
5 12 10 7 2 4 13 14 15 19
右側のソートが終了しています。
次は、左側に関して同じようにソートしていけば、昇順にソートされることがわかります。
今回は、ピボットを真ん中の値としましたが、先頭の値をピボットとしてもいいですし、
ソートに関して、効率のよい値をピボットにするのがベストです。
では、最後にc++のソースコートを載せます。
/*
array = ソートしたいデータ
begin = 要素の最初
end = 要素の末尾
*/
void QuickSort(int array[], int begin, int end)
{
int i = begin;
int j = end;
int pivot;
int temp;
pivot = array[ ( begin + end ) / 2 ]; // 中央の値をpivotにする
while( 1 )
{
while( array[i] < pivot ){ ++i; } /* 枢軸以上の値が見つかるまで右方向へ進めていく */
while( array[j] > pivot ){ --j; } /* 枢軸以下の値が見つかるまで左方向へ進めていく */
if( i >= j )break; // 軸がぶつかったらソート終了
// 入れ替え
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
// 軸の左側をソートする
if( begin < i - 1 ){ QuickSort( array, begin, i - 1 ); }
// 軸の右側をソートする
if( j + 1 < end ){ QuickSort( array, j + 1, end ); }
}
