ソートはアルゴリズムの基本
ソートは「並び替え」という最も基本的な処理でありながら、アルゴリズムの多様性・計算量・トレードオフを学ぶ絶好の題材です。
バブルソート O(n²)
隣り合う要素を比較して交換を繰り返す。最もシンプルだが最も遅い。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 交換が1回も起きなければ完了
break
return arr
# 例: [5, 3, 1, 4, 2]
# パス1: [3,1,4,2,5] → 最大値5が末尾へ
# パス2: [1,3,2,4,5] → 次の最大値4が確定
# ...特徴:
- 最良: O(n)（すでにソート済み＋早期終了）
- 最悪: O(n²)
- 安定ソート（同じ値の相対順序が保たれる）
- 実用的にはほぼ使わない
選択ソート O(n²)
未整列部分から最小値を選んで先頭と交換する。
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 例: [5, 3, 1, 4, 2]
# i=0: 最小値1を選んで先頭と交換 → [1, 3, 5, 4, 2]
# i=1: 残りの最小値2を選んで2番目と交換 → [1, 2, 5, 4, 3]
# ...特徴:
- 常に O(n²)（最良・最悪ともに）
- 交換回数が O(n) と少ない
- 不安定ソート
挿入ソート O(n²)
手持ちのトランプを整列させるイメージ。小さい n や「ほぼソート済み」のデータに強い。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 例: [5, 3, 1, 4, 2]
# i=1: key=3, [3,5,1,4,2]
# i=2: key=1, [1,3,5,4,2]
# i=3: key=4, [1,3,4,5,2]
# i=4: key=2, [1,2,3,4,5]特徴:
- 最良: O(n)（ほぼソート済み）
- 最悪: O(n²)
- 安定ソート
- 小規模データでは定数が小さく実用的
- ティムソート（Python/Java の組み込み）の内部でも使われる
マージソート O(n log n)
「分割統治法」の代表例。配列を半分に分け、再帰的にソートしてマージする。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result動作イメージ:
[5, 3, 1, 4, 2]
→ [5, 3] + [1, 4, 2] # 分割
→ [5]+[3] + [1]+[4,2] # さらに分割
→ [3,5] + [1]+[4]+[2] # 1要素をマージ
→ [3,5] + [1,2,4] # マージ
→ [1,2,3,4,5] # 最終マージ特徴:
- 常に O(n log n)
- 安定ソート
- 空間 O(n)（追加メモリが必要）
- 連結リストのソートに最適
クイックソート O(n log n) 平均
ピボットを選んで、小さい要素を左・大きい要素を右に分割する。
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1特徴:
- 平均: O(n log n)
- 最悪: O(n²)（既ソート済み＋末尾ピボットの場合）
- 不安定ソート
- 空間 O(log n)（スタック）
- キャッシュ効率が高く実践最速クラス
各ソートアルゴリズムの比較
| アルゴリズム | 平均 | 最悪 | 空間 | 安定 |
|---|---|---|---|---|
| バブルソート | O(n²) | O(n²) | O(1) | ✅ |
| 選択ソート | O(n²) | O(n²) | O(1) | ❌ |
| 挿入ソート | O(n²) | O(n²) | O(1) | ✅ |
| マージソート | O(n log n) | O(n log n) | O(n) | ✅ |
| クイックソート | O(n log n) | O(n²) | O(log n) | ❌ |
| ヒープソート | O(n log n) | O(n log n) | O(1) | ❌ |
使い分け
一般的なケース
→ 言語組み込みのソートを使う（最適化済み）
Python: sorted() / list.sort() — ティムソート O(n log n)
JavaScript: Array.sort() — V8ではティムソート
Java: Arrays.sort() — プリミティブ型はクイック、オブジェクトはマージ
小さな配列（n < 20）または「ほぼソート済み」
→ 挿入ソートが実用上速い
安定性が必要（同じキーの相対順序を保ちたい）
→ マージソートまたはティムソート
メモリが厳しい
→ ヒープソート（空間O(1)、安定ではないが最悪でもO(n log n)）ティムソート — Python/JavaScript の実装
Python の sorted() と list.sort() が使うティムソートは、挿入ソートとマージソートを組み合わせたハイブリッドアルゴリズムです。
- 現実のデータには「ほぼ整列済みの部分列（ラン）」が多い
- 小さなランには挿入ソート、大きなランのマージにはマージソートを使う
- 最良 O(n)、最悪 O(n log n)、安定
まとめ
- 面接・実務では組み込みソートを使うのが正解
- ソートアルゴリズムの学習価値は、分割統治・安定性・トレードオフの思考訓練にある
- 「なぜクイックソートは速いのか」「なぜ最悪 O(n²) なのか」を語れると信頼度が上がる