今回はクイックソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。
クイックソートとは
まずソートとはデータを並べ替えることをいい、クイックソートとは、軸となる基準値より小さなデータと大きなデータに振り分け、データを2つに分けることを再帰的に繰り返しながらソートするという方法になります。
①軸となる基準値(pivot)をデータの中から決める(ランダムでよい)
②配列の左から pivot 以上の値を、右から pivot 未満の値を探し、交換する。
この操作を、「左」と「右」が逆転するまで続ける。
③「左」と「右」が逆転したら、データを2つに分け、それぞれに対し①②を繰り返す。
では実際に、以下のデータをクイックソートしてみます。
6,2,7,4,9,1,5,8,0,3
pivot の決め方は何でもよいので、今回は配列の最初の2つのデータ(6,2)のうち大きい方(6)に設定することにします。
6,2,7,4,9,1,5,8,0,3
では左から pivot 以上の値を、右から pivot 未満の値を探します。
6,2,7,4,9,1,5,8,0,3
そして交換します。
3,2,7,4,9,1,5,8,0,6
再び探していきます。
3,2,7,4,9,1,5,8,0,6
そして交換します。
3,2,0,4,9,1,5,8,7,6
再び探していきます。
3,2,0,4,9,1,5,8,7,6
そして交換します。
3,2,0,4,5,1,9,8,7,6
再び探していきます。
3,2,0,4,5,1,9,8,7,6
ここで「左」と「右」が逆転したため探索を終え、
「左」より前のデータ群と、「左」以降のデータ群に分けます。
3,2,0,4,5,1 | 9,8,7,6
ここで注目してほしいのが、左側には pivot 未満のデータが、右側には pivot 以上のデータが
自動的に振り分けられているということです。
続けてそれぞれのデータ群に対し、同様の処理を繰り返していくことで昇順にソートすることができます。
実装
function quickSort(array, min, max) {
let pivotIndex = findPivot(array, min, max);
if (pivotIndex > -1) {
let pivot = array[pivotIndex];
let l = arrange(array, min, max, pivot);
quickSort(array, min, l-1);
quickSort(array, l, max);
}
}
function findPivot(array, min, max) {
let pivot = array[min];
let k = min + 1;
while (k <= max) {
if (array[k] == pivot) {
k++;
}else{
if (array[k] > pivot) {
return k;
}else{
return min;
}
}
}
return -1;
}
function arrange(array, min, max, pivot) {
let l = min;
let r = max;
while (l <= r) {
let tmp = array[l];
array[l] = array[r];
array[r] = tmp;
while (array[l] < pivot) {
l++;
}
while (array[r] >= pivot) {
r--;
}
}
return l;
}
let datas= [
6,2,7,4,9,1,5,8,0,3
];
let min = 0;
let max = datas.length-1;
quickSort(datas, min, max);
console.log(datas);//0,1,2,3,4,5,6,7,8,9と表示
解説
まず、簡単に3つの関数の役割を確認します。
関数名 | 役割 |
---|---|
quickSort | 引数の配列をクイックソートする |
findPivot | pivot となるデータのインデックスを返す |
arrange | 引数の配列のデータを入れ替え、「左」のインデックスを返す |
では、quickSort 関数の中身をみていきます。
まず最初に findPivot 関数で pivot のインデックスを取得しています。
let pivotIndex = findPivot(array, min, max);
いったん findPivot 関数をみてみます。
配列の最初のデータを仮に pivot と設定し、ふたつめのデータのインデックスを k と置きます。
let pivot = array[min];
let k = min + 1;
もし最初の2つのデータが同じ値なら、異なる値が見つかるまで探し、その後大きい方のデータのインデックスを pivot として返します。
配列にデータが1つしかない、あるいは全てのデータが同じ値の場合は-1を返します。
while (k <= max) {
if (array[k] == pivot) {
k++;
}else{
if (array[k] > pivot) {
return k;
}else{
return min;
}
}
}
return -1;
では quickSort 関数にもどります。
取得した pivot のインデックスが-1でなければ、配列から pivot を取得し arrange 関数を呼び出します。
if (pivotIndex > -1) {
let pivot = array[pivotIndex];
let l = arrange(array, min, max, pivot);
...
}
では arrange 関数をみてみます。
min, max をそれぞれ l ( left ) , r ( right ) に入れ、l が r より大きくなるまで交換を行い、最終的な l の値を返します。
let l = min;
let r = max;
while (l <= r) {
let tmp = array[l];
array[l] = array[r];
array[r] = tmp;
while (array[l] < pivot) {
l++;
}
while (array[r] >= pivot) {
r--;
}
}
return l;
では quickSort 関数にもどります。
arrange 関数で取得した l を軸に2つのデータ群に分け、それぞれに対し quickSort 関数を呼び出します。
let l = arrange(array, min, max, pivot);
quickSort(array, min, l-1);
quickSort(array, l, max);
このように、quickSort 関数を再帰的に繰り返すことでソートすることができます。
ちなみに、自分自身の関数を呼び出す関数のことを、再帰関数といいます。
下の記事で解説しているので、よかったらどうぞ!
参考書
コメント