前回までで、単純なソートアルゴリズムの解説が完了した。
今回から、高速なソートアルゴリズムに入っていこう。
まずは、クイックソートと呼ばれるソートをご紹介する。
そのために必要な前提知識は、以前解説したものがあるのでそちらを参照してもらおう。
考え方が複雑化してくるから、
一個一個落ち着いて処理を追おう!
前提知識
前提として、二つの知識が必要となる。
- 再帰
- 分割統治法
これらについては、以下記事で解説しているので、そちらをご参照頂きたい。
【再帰・分割統治法】高速なソートアルゴリズム前提知識 -考え方編- | Shino’s Mind Archive
クイックソート
実は上で出した記事の中で紹介してしまっているのだが、正確なアルゴリズムとして改めて紹介しよう。
入力はn個の要素を持つdata
配列、並び替える要素は整数としておこう。
出力も、いつも通り並び替えが終わったdata
配列だ。
まず、data
配列の中から適当な要素を一つ選択する。
これを、data[v]
としておこう。
このdata[v]
のことを、枢軸、あるいはpivotと呼ぶ。
そして、残りのデータを二つに分割する。
- 枢軸
data[v]
よりも小さいデータ - 枢軸
data[v]
よりも大きいデータ
そして、data[v]
よりも小さいデータ、data[v]
、data[v]
よりも大きいデータという順番に並び替える。
その後、data[v]
よりも小さいデータで同じことをし、data[v]
よりも大きいデータでも同じことをする。
これを繰り返し、分割された後のデータが一つになったら処理を上に戻す。
そして、それが全て終わったら、ソートが完了しているのだ。
文章の説明だとちょっと分かりづらいと思うので、具体例で見ていこう。
あまり数が多くなると大変なので、5個の要素で見ていこう。
i | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data[i] | 5 | 2 | 4 | 1 | 3 |
まず、枢軸を選ぶのだが、これはどこでもいい。
なので、一番後ろのdata[4]=3
を枢軸としよう。
そして、まずは3より小さいデータを左に、大きいデータを右に持ってくる。
i | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data[i] | 2 | 1 | 3 | 5 | 4 |
次に、左と右の範囲で同じことをしてあげる。
まずは左から見ていこう。
同じように一番後ろのdata[1]=1
を枢軸として、大きさによって左右に振り分ける。
…とはいっても、2しかないので、順番を入れ替えるだけだ。
i | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data[i] | 1 | 2 | 3 | 5 | 4 |
ここで、左側は分割後の要素が1個になったので、終了だ。
次に右側、同じように考えると、枢軸がdata[4]=4
なので…
i | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data[i] | 1 | 2 | 3 | 4 | 5 |
このようになる。
こちらも、分割後の要素が一つなので完了だ。
というわけで、両側ともに完了したため、全体としてもソートが完了となる。
大まかな流れは分かっただろうか。
クイックソートの計算量
クイック、という名前がついているくらいだから速いのだろうと思われる方、正解だ。
詳細な考え方は割愛するが、このクイックソートは計算量\(O(n \log(n))\)になる。
単純なソートアルゴリズムが\(O(n^2)\)だったのと比較すれば高速なことが分かってもらえると思う。
なお、クイックソートはその名の通り内部整列という分類中最速を誇る。
まさに、名前通りのソートだ。
クイックソートのサンプルプログラム
最後に、サンプルソースを提示しておこう。
なお、今回は二つの関数に処理を分けている。
まず、QuickSort()
がメインの処理だ。
引数は順番に、ソートする配列、ソートする範囲の左端、右端だ。
戻り値はなく、入力された配列をそのままソートする。
次に、partition()
が枢軸を決定し、その後左と右に分ける処理を行う。
引数はQuickSort()
と同じもの、同じ並びになっている。
こちらの戻り値は、枢軸となるデータが最終的にどこになったかの添え字だ。
function QuickSort(data, left, right){
console.log("left:right = " + left + ":" + right + " , " + data);
if(left >= right){
return;
}
let v = partition(data, left, right);
QuickSort(data, left, v - 1);
QuickSort(data, v + 1, right);
}
function partition(data, left, right){
let i = left;
let j = right - 1;
let pivot = data[right];
while(true){
while(data[i] < pivot){
i++;
}
while(i < j && pivot < data[j]){
j--;
}
if(i >= j){
break;
}
let tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
let tmp = data[i];
data[i] = data[right];
data[right] = tmp;
return i;
}
partition()
の動きをちょっと補足しておこう。
左右から順番に数を見ていく。
左からi
で回して、枢軸より大きい数を探す。
右からj
で回して、枢軸より小さい数を探す。
このとき、i
とj
が交差していれば、元々枢軸より小さいものが左、大きいものが右にあるので、枢軸だけ入れ替えれば完了だ。
そうでなければ、i
とj
のデータを入れ替える。
これを繰り返し、データを左右に分割していくのだ。
で、最後に枢軸となるデータを適した箇所に入れてあげる、という処理になっている。
なお、QuickSort()
の先頭で現在どこの範囲を見ていて、そのときの配列がどうなっているかを出力している。
これを見ながら、どう動いているか確認してほしい。
最悪なケースを回避するために
実は、最悪のケースというものが存在する。
何かと言うと、すでに整列済みのデータだ。
こうすると、分割しようにも常に片方に全てのデータが寄ってしまう。
これを回避するために、常に左右に分割されるようにしたい。
そこで、複数個所のデータを持ってきて、その中央値を取る、というアプローチが対策として挙げられる。
例えば、データの先頭、真ん中、末尾を比べて、その中央値を取れば、必ず左右にデータが分割される。
このようにすれば、最悪なケースを避けることができるのだ。
これについては、サンプル等は提示しないので、是非チャレンジしてみてほしい。
おわりに
今回は高速なソートアルゴリズムの一つであるクイックソートを解説した。
ちょっと考え方が複雑になってきたので、落ち着いて一個一個動きを確認しながら進めよう。
次回は、二つ目のマージソートについて解説する。
今回のクイックソートと何が違うかをしっかり確認しながら、進めて欲しい。
コメント