JavaScriptで分割統治法を実装してクイックソート（QuickSort）を作る方法

クイックソート（QuickSort）とは

クイックソートは、代表的な分割統治法（Divide and Conquer）に基づくソートアルゴリズムです。各パスごとに基準となる「ピボット」と呼ばれる要素を1つ選び、ピボットより小さい値をすべて左側へ、大きい値をすべて右側へ配置します（昇順ソートの場合。降順ソートならこの逆になります）。この操作を再帰的に繰り返すことで、配列全体が徐々に整列されていきます。

平均計算量は O(n log n) と非常に高速で、実務でも広く利用されている効率的なソート手法です。

実装例

ここでは、数値の配列を受け取り、クイックソートを使って昇順に並べ替えるJavaScript関数を実装してみましょう。コードは以下の通りです。

const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];

// 配列から「ピボット」要素を見つけ、他の全要素と比較しながら、
// 値に応じてピボットより前か後ろへ要素を振り分ける
const quickSort = (arr, left = 0, right = arr.length - 1) => {
    let len = arr.length, index;
    if (len > 1) {
        index = partition(arr, left, right);
        if (left < index - 1) {
            quickSort(arr, left, index - 1); // 左側の部分配列を再帰的にソート
        }
        if (index < right) {
            quickSort(arr, index, right); // 右側の部分配列を再帰的にソート
        }
    }
    return arr;
};

const partition = (arr, left, right) => {
    let middle = Math.floor((right + left) / 2),
        pivot = arr[middle],
        i = left,  // 配列の先頭要素からスタートするポインタ
        j = right; // 配列の末尾要素からスタートするポインタ

    while (i <= j) {
        // 左側の値がピボット以上になるまで、左ポインタを右へ進める
        while (arr[i] < pivot) {
            i++;
        }
        // 右側の値がピボット以下になるまで、右ポインタを左へ進める
        while (arr[j] > pivot) {
            j--;
        }
        // 左ポインタが右ポインタ以下の場合は、両者の値を入れ替える
        if (i <= j) {
            [arr[i], arr[j]] = [arr[j], arr[i]]; // ES6の分割代入によるスワップ
            i++;
            j--;
        }
    }
    return i;
};

console.log(quickSort(arr));

実行結果

コンソールには次のように出力されます。

[
    2,   3,    4,  6, 23,
    23,  34,   34, 43, 54,
    54, 232, 3434
]

処理のポイント

• ピボットの選択：この実装では配列の中央にある要素をピボットとしています。中央付近を選ぶことで、ほぼ整列済みの入力データに対しても性能が極端に劣化しにくくなります。
• partition関数：左右2つのポインタを用意し、ピボットとの大小関係に応じて要素を入れ替えながら配列を分割します。戻り値となるインデックスが、次回の分割境界の目安になります。
• 再帰呼び出し：分割された左右の部分配列それぞれに対してquickSortを再帰的に適用することで、最終的に配列全体がソートされます。

なお、クイックソートの平均計算量は O(n log n) ですが、ピボットの選び方が不適切な場合は最悪で O(n²) まで性能が低下する点にも注意しておきましょう。