ソートアルゴリズムで最も高速といわれているクイックソートにチャレンジしてみます。
でもwikipediaの解説を見てみると、最も高速と言われながらも、データの並びや数によっては、必ずしも早いわけではないそうだ。
少し冷めてしまいそうなアルゴリズムだが、今までと何が違うかを考えながら仕様を確率してみたいと思う。
ソース
function mid(x , y , z){
if (x < y) {
if (y < z){
return y;
}
else if (z < x){
return x;
}
else{
return z;
}
}
else {
if (z < y){
return y;
}
else if (x < z){
return x;
}
else{
return z;
}
}
}
function quickSort(numbers , begin , end){
if((end - begin) <= 1){return numbers}
// 左辺と右辺の開始位置を定義
begin = (typeof begin === "undefined")?0:begin;
end = (typeof end === "undefined")?numbers.length -1:end;
var left = begin;
var right = end;
if(begin >= end){return numbers}
// ピボット(中央の値)
var pivot = mid(numbers[left] , numbers[left+parseInt((right-left)/2,10)] , numbers[right]);
// ソート処理実行（pivotが交差するまで続行）
while(1){
// 左辺のpivotよりも大きい値見つける
while(numbers[left] < pivot){left++}
// 右辺のpivotよりも小さい値をみつける
while(numbers[right] > pivot){right--}
//pivotが交差したら終了
if(left >= right){break}
// 値の入れ替え処理
var tmp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = tmp;
// 繰り返し対応
left++;
right--;
}
// pivotの左辺のソート処理
numbers = quickSort(numbers , begin , left);
// pivotの右辺のソート処理
numbers = quickSort(numbers , right , end);
return numbers;
}
quickSort([20,10,2,12,7,16,8,13,1]);
解説
サンプルソース作りが非常に難航しました。
それは、このアルゴリズムをちゃんと理解しておらず、pivotをずっと分岐点だと勘違いしていたからです。
pivotは、あくまで数値の基準値であって、それのポジションは全く必要がなかったからですね。
さらに、wikipediaや他のサイトのソースコードでC++などの言語で書かれていたので、それを元に移植してみたんですが、エラーに悩まされて、ようやく解決したという事でした。
mid関数
pivotを抽出する関数で、配列の先頭、中間、最終の数値を送って、３つの値の中間値を取得するようになってます。
これをもう少し簡略できれば、もう少しシンプルにかけたのだが、これを曖昧にすることで、ソート精度に影響がでるかどうかがわからないので、このまま続行しました。
関数内の禁則処理
quickSort関数の冒頭にある
if((end - begin) < = 1){return numbers}
や
if(begin >= end){return numbers}
などを書いておかないと、無限ループが発生してしまうので、少し慎重気味に書いておきました。
再帰処理
// pivotの左辺のソート処理
numbers = quickSort(numbers , begin , left);
// pivotの右辺のソート処理
numbers = quickSort(numbers , right , end);
quickSort処理内でquickSort関数を実行することで、配列を次々と処理する再帰処理を実現してます。
サーバ内のフォルダ構成を表示する際などにもこのやり方をよく使いますが、初心者が慣れていないと無限ループしちゃうので、使い慣れましょうね。
関連記事
アルゴリズム学習
0 件のコメント:
コメントを投稿