ソートアルゴリズム比較

計算量一覧

アルゴリズム最良平均最悪安定
バブルソートO(n)O(n)O(n2)O(n^2)O(n2)O(n^2)Yes
マージソートO(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)Yes
クイックソートO(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(n2)O(n^2)No

クイックソートの実装例

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter((x) => x < pivot);
  const middle = arr.filter((x) => x === pivot);
  const right = arr.filter((x) => x > pivot);

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

TypeScript

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter((x) => x < pivot);
  const middle = arr.filter((x) => x === pivot);
  const right = arr.filter((x) => x > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

JavaScript

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter((x) => x < pivot);
  const middle = arr.filter((x) => x === pivot);
  const right = arr.filter((x) => x > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

マージソートの特徴

  • 安定ソート: 同じ値の要素の順序が保持される
  • 空間計算量: O(n)O(n) の追加メモリが必要
  • 分割統治法: 再帰的に半分に分割して結合