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