ソートアルゴリズム

バブルソート（Bubble Sort）

隣り合う要素を比較し、大きい方を右にずらしていく最もシンプルなソートです。 計算量は O(n^2) で、大量データには不向きですが理解しやすいアルゴリズムです。

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 隣同士を入れ替え
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

選択ソート（Selection Sort）

未ソート部分から最小値を見つけて先頭に配置する操作を繰り返します。 計算量は O(n^2) ですが、交換回数がバブルソートより少ないのが特徴です。

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    // 最小値を先頭に移動
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

console.log(selectionSort([29, 10, 14, 37, 13]));
// [10, 13, 14, 29, 37]

マージソート（Merge Sort）

配列を半分に分割し続け、それぞれをソートしてからマージ（統合）する分割統治法の代表的なアルゴリズムです。 計算量は O(n log n) で安定しており、大量データに強いです。

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

クイックソート（Quick Sort）

ピボット（基準値）を選び、それより小さい要素と大きい要素に分割して再帰的にソートします。 平均計算量は O(n log n) で、実用上最も高速なソートの1つです。 ただし最悪ケースでは O(n^2) になることがあります。

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([10, 7, 8, 9, 1, 5]));
// [1, 5, 7, 8, 9, 10]

ソートアルゴリズムの比較

JavaScriptの Array.prototype.sort() は、 多くのエンジンでTimSort（マージソートと挿入ソートのハイブリッド）を採用しています。