ソートアルゴリズム#
ソートアルゴリズムはデータを特定の順序に並び替えるアルゴリズム。用途やデータの特性によって最適な手法が異なる。
主要アルゴリズムの比較#
アルゴリズム |
最悪 |
平均 |
最良 |
空間 |
安定 |
in-place |
|---|---|---|---|---|---|---|
バブルソート |
\(O(n^2)\) |
\(O(n^2)\) |
\(O(n)\) |
\(O(1)\) |
✓ |
✓ |
選択ソート |
\(O(n^2)\) |
\(O(n^2)\) |
\(O(n^2)\) |
\(O(1)\) |
✗ |
✓ |
挿入ソート |
\(O(n^2)\) |
\(O(n^2)\) |
\(O(n)\) |
\(O(1)\) |
✓ |
✓ |
マージソート |
\(O(n\log n)\) |
\(O(n\log n)\) |
\(O(n\log n)\) |
\(O(n)\) |
✓ |
✗ |
クイックソート |
\(O(n^2)\) |
\(O(n\log n)\) |
\(O(n\log n)\) |
\(O(\log n)\) |
✗ |
✓ |
ヒープソート |
\(O(n\log n)\) |
\(O(n\log n)\) |
\(O(n\log n)\) |
\(O(1)\) |
✗ |
✓ |
計数ソート |
\(O(n+k)\) |
\(O(n+k)\) |
\(O(n+k)\) |
\(O(n+k)\) |
✓ |
✗ |
基数ソート |
\(O(d(n+b))\) |
\(O(d(n+b))\) |
\(O(d(n+b))\) |
\(O(n+b)\) |
✓ |
✗ |
選択の指針#
汎用: Python の
sorted()/list.sort()（Timsort）を使う小配列 / ほぼソート済み: 挿入ソート
最悪保証が必要 + in-place: ヒープソート
安定 + 最悪保証: マージソート
実用最速（平均）: クイックソート（median-of-3 や乱択ピボット）
整数 + 値域が小さい: 計数ソート
整数 + 値域が広い: 基数ソート