JavaScript クイックソート

クイックソート

クイックソートはその名にクイックとあるように処理速度の速いコードです。
「再帰」という考え方を使っています。

アルゴリズムのイメージ

・配列の中の小さいデータを左側に集め、大きいデータを右側に集めるて大小二つのグループをつくる。
・それぞれのグループで同じように小さいデータを左側に、大きいデータを右側に集めてさらに大小二つのグループをつくる。
・上記の処理を繰り返す事によって配列全体を小さいデータから大きいデータに順番に並べる。
・クイックソートでは処理速度を速めるために、交換する必要のある値だけを交換する。
・クイックソートでは「再帰」を利用する

交換する必要のある値だけを交換

クイックソートでは、交換する必要のある値だけを交換するために「ピボット(大小の値の分岐点)」を決めます。
ピボットの決め方は色々ありますが、本記事では「真ん中にある値」ですすめます。
アイデアとしては、ピボットを基準に左側を調べてピボットより大きい値を見つけます。
同時に、ピボットの右側を調べてピボットより小さい値を見つけます。二つがそろった時に値を交換すれば無駄な処理を省くことができるのです。

「再帰」を利用

クイックソートでは再帰を利用します。再帰とは「自分で自分自身を呼び出す」ことです。
先頭から末尾まで順番に探していくような「並列的な繰り返し」はループ処理で行います。しかし、「分割した部分に対してさらに同じように分割する」といった階層的に一段深い処理に対しては再帰を利用します。
再帰のイメージは自分と同じ役割をこなせる分身をつくって分身に作業をさせる、でしょうか。分身がさらに分身をつくっていく感じです。
「人間は反復し、神は再帰する。」というような言葉もあります。
注意点としては、階層が深くなるにつれて消費のメモリが大きくなること、無限の繰り返しを止めるために終了条件をきめておくことです。

手順

前提 未整列のデータを用意する。
1 再帰のための関数を作成する。引数にソートの開始位置と終了位置を設定する。
2 開始位置と終了位置からピボットを決めて、「交換する必要のある値だけを交換」して大小のグループに分割します。
3 分割したグループに対してさらに大小のグループに分けるように再帰的に処理を繰り返します。
4 分割できなくなるまで処理を繰り返しを行えばソート完了

コード

script.js

//クイックソート関数
function quickSort(startID,endID){
    //範囲の間にある値をピポットに設定する
    var pivot = a[Math.floor((startID + endID)/2)];
    //引数を左端、右端として変数にいれる
    var left = startID;
    var right = endID;

    //ピポットより小さい値を左側へ、大きい値を右側へ分割する
    while(true){
        //leftの値がpivotより小さければleftを一つ右へ移動する
        while(a[left]<pivot){
            left++;
        }
        //rightの値がpivotより小さければrightを一つ左へ移動する
        while(pivot<a[right]){
            right--;
        }
        //leftとrightの値がぶつかったら、そこでグループ分けの処理を止める。
        if(right <= left){
            break;
        }

        //rightとrightの値がぶつかっていない場合、leftとrightを交換
        //交換後にleftを後ろへ、rightを前へ一つ移動する
        var tmp =a[left];
        a[left] =a[right];
        a[right] =tmp;
        left++;
        right--;
    }

    //左側に分割できるデータがある場合、quickSort関数を呼び出して再帰的に処理を繰り返す。
    if(startID < left-1){
        quickSort(startID,left-1);
    }
    //右側に分割できるデータがある場合、quickSort関数を呼び出して再帰的に処理を繰り返す。
    if(right+1 < endID){
        quickSort(right+1,endID);
    }
}

   //未整列の配列
   var a = [3,7,2,4,6,1,9,8,5];
   //先頭から末尾までソートする
   quickSort(0,a.length-1);

//結果の表示    
console.log(a);