JavaScriptで再帰を使ったクイックソートの実装方法を解説

はじめに

数値の配列を受け取り、クイックソートのアルゴリズムを適用して昇順または降順に並べ替えるJavaScript関数を作成してみましょう。本記事では、再帰処理を活用したクイックソートの実装方法を、実際のコード例とともにわかりやすく解説します。

クイックソートのアルゴリズム

クイックソートは、以下の手順で動作する代表的なソートアルゴリズムです。

ステップ1 − 配列内の任意の要素を「ピボット」として選択します(先頭や末尾が一般的ですが、どの要素を選んでも問題ありません)

ステップ2 − ピボットを基準に配列を分割(パーティション)します

ステップ3 − 左側のパーティションに対して再帰的にクイックソートを適用します

ステップ4 − 右側のパーティションに対して再帰的にクイックソートを適用します

クイックソートの平均計算量および最良ケースの時間計算量はO(n log n)と非常に高速ですが、最悪の場合にはO(n²)までパフォーマンスが低下する点に注意が必要です。

コードの構成要素

• swap関数： 配列内の2つの要素の位置を入れ替えるための補助関数です。
• partition関数： 配列の中央にある要素をピボットとして選び、ピボットより小さい要素を左側へ、大きい要素を右側へ移動させます。
• quickSort関数： パーティションの結果をもとに、左右それぞれの部分配列に対して自分自身を再帰的に呼び出し、全体を整列させます。

実装例

実際のコードは以下の通りです。

const arr = [5,3,7,6,2,9];
const swap = (arr, leftIndex, rightIndex) => {
   let temp = arr[leftIndex];
   arr[leftIndex] = arr[rightIndex];
   arr[rightIndex] = temp;
};
const partition = (arr, left, right) => {
   let pivot = arr[Math.floor((right + left) / 2)];
   let i = left;
   let j = right;
   while (i <= j) {
      while (arr[i] < pivot) {
         i++;
      };
      while (arr[j] > pivot) {
         j--;
      };
      if (i <= j) {
         swap(arr, i, j); // 2つの要素を入れ替え
         i++;
         j--;
      };
   };
   return i;
}
const quickSort = (arr, left = 0, right = arr.length - 1) => {
   let index;
   if (arr.length > 1) {
      index = partition(arr, left, right);
      if (left < index - 1) {
         quickSort(arr, left, index - 1);
      };
      if (index < right) {
         quickSort(arr, index, right);
      };
   }
   return arr;
}
let sortedArray = quickSort(arr);
console.log(sortedArray);

実行結果

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

[ 2, 3, 5, 6, 7, 9 ]

まとめ

このように、ピボットの選択・パーティション分割・再帰呼び出しというシンプルな仕組みを組み合わせることで、効率的に配列をソートできます。デフォルト引数(left = 0、right = arr.length - 1)を活用することで、呼び出し側のコードも簡潔になっています。