高速なソートアルゴリズム「クイックソート」を解説！

前回までで、単純なソートアルゴリズムの解説が完了した。

今回から、高速なソートアルゴリズムに入っていこう。

まずは、クイックソートと呼ばれるソートをご紹介する。

そのために必要な前提知識は、以前解説したものがあるのでそちらを参照してもらおう。

シノ

考え方が複雑化してくるから、
一個一個落ち着いて処理を追おう！

前提知識

前提として、二つの知識が必要となる。

• 再帰
• 分割統治法

これらについては、以下記事で解説しているので、そちらをご参照頂きたい。

【再帰・分割統治法】高速なソートアルゴリズム前提知識 -考え方編- | 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個の要素で見ていこう。

まず、枢軸を選ぶのだが、これはどこでもいい。

なので、一番後ろのdata[4]=3を枢軸としよう。

そして、まずは3より小さいデータを左に、大きいデータを右に持ってくる。

次に、左と右の範囲で同じことをしてあげる。

まずは左から見ていこう。

同じように一番後ろのdata[1]=1を枢軸として、大きさによって左右に振り分ける。

…とはいっても、2しかないので、順番を入れ替えるだけだ。

ここで、左側は分割後の要素が1個になったので、終了だ。

次に右側、同じように考えると、枢軸がdata[4]=4なので…

このようになる。

こちらも、分割後の要素が一つなので完了だ。

というわけで、両側ともに完了したため、全体としてもソートが完了となる。

大まかな流れは分かっただろうか。

クイックソートの計算量

クイック、という名前がついているくらいだから速いのだろうと思われる方、正解だ。

詳細な考え方は割愛するが、このクイックソートは計算量\(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()の先頭で現在どこの範囲を見ていて、そのときの配列がどうなっているかを出力している。

これを見ながら、どう動いているか確認してほしい。

最悪なケースを回避するために

実は、最悪のケースというものが存在する。

何かと言うと、すでに整列済みのデータだ。

こうすると、分割しようにも常に片方に全てのデータが寄ってしまう。

これを回避するために、常に左右に分割されるようにしたい。

そこで、複数個所のデータを持ってきて、その中央値を取る、というアプローチが対策として挙げられる。

例えば、データの先頭、真ん中、末尾を比べて、その中央値を取れば、必ず左右にデータが分割される。

このようにすれば、最悪なケースを避けることができるのだ。

これについては、サンプル等は提示しないので、是非チャレンジしてみてほしい。

おわりに

今回は高速なソートアルゴリズムの一つであるクイックソートを解説した。

ちょっと考え方が複雑になってきたので、落ち着いて一個一個動きを確認しながら進めよう。

次回は、二つ目のマージソートについて解説する。

今回のクイックソートと何が違うかをしっかり確認しながら、進めて欲しい。