JavaScriptのクイックソートで数値配列をソートする方法

本記事では、数値の配列を受け取り、クイックソート（Quick Sort）アルゴリズムを使って昇順に並べ替えるJavaScript関数の実装方法を解説します。

クイックソートとは

クイックソートは、代表的な「分割統治法（Divide and Conquer）」に基づくソートアルゴリズムです。各パスごとにピボット（pivot）と呼ばれる基準値を1つ選び、ピボットより小さい要素をすべて左側へ、大きい要素をすべて右側へ移動させます。この操作を再帰的に繰り返すことで、配列全体を効率よく並べ替えます。

平均計算量は O(n log n) と高速であり、大規模なデータのソートにも適しています。

実装コード

以下が実際のコード例です。配列の中間要素をピボットとして選択し、左右のポインタを使って要素を交換しながら分割を行います。

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));

処理の流れのポイント

• quickSort関数：配列の長さが1より大きい場合のみ処理を実行し、partition関数で得られた分割位置を基準に、左右の部分配列に対して再帰的にソートを行います。
• partition関数：中央の要素をピボットとし、左ポインタと右ポインタを動かしながら条件を満たす要素同士を交換します。ES6の分割代入構文を使うことで、一時変数なしで簡潔にスワップできます。

出力結果

コンソールには以下のようにソート済みの配列が出力されます。

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

このように、クイックソートを自前で実装することで、ソートの仕組みを深く理解できるだけでなく、面接やコーディングテストでも役立つ知識となります。ぜひ実際にコードを動かして挙動を確認してみてください。