ソートアルゴリズム — バブル、選択、マージ
このトピックを終えると
3つのソートアルゴリズムの動作を説明でき、それぞれの時間計算量と長所・短所を比較できます。
なぜソートを学ぶのか
ソートは、プログラミングにおいて最も基本的な、そして最も研究されている問題の一つです。実務で直接ソートアルゴリズムを実装することはあまりありません（Pythonのsorted()を使用すればよい）、しかしソートアルゴリズムを学ぶことで、アルゴリズム的思考力が鍛えられます。問題をどのように分割し、反復し、最適化するのか、という考え方です。
バブルソート — 最も直感的
隣り合う2つの要素を比較し、順番が間違っている場合は交換します。これを全体がソートされるまで繰り返します。
def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr
# [5, 3, 8, 1, 2] → [3, 5, 1, 2, 8] → ... → [1, 2, 3, 5, 8]動作過程（1回の反復）：
[5, 3, 8, 1, 2]
5>3 → 交換 → [3, 5, 8, 1, 2]
5<8 → 維持 → [3, 5, 8, 1, 2]
8>1 → 交換 → [3, 5, 1, 8, 2]
8>2 → 交換 → [3, 5, 1, 2, 8] ← 8が一番後ろに大きな値が泡のように上に「浮き上がってくる」様子から、バブルソートと呼ばれます。時間計算量：O(n²)。理解しやすいですが、速度は遅いです。
選択ソート — 最小値をソート済みの領域に配置
全体の中から最も小さい値を見つけて、一番最初の位置に配置します。次に、残りの部分から最も小さい値を見つけて、2番目の位置に配置します。これを繰り返します。
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, 8, 1, 2]
最小=1 → [1, 3, 8, 5, 2]
最小=2 → [1, 2, 8, 5, 3]
最小=3 → [1, 2, 3, 5, 8]
完了時間計算量：O(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, 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, 8, 1, 2]
↙ ↘
[5, 3, 8] [1, 2]
↙ ↘ ↓
[5] [3,8] [1, 2]
↓ ↓
[5] [3,8] [1,2]
↘ ↙ ↓
[3,5,8] [1,2]
↘ ↙
[1, 2, 3, 5, 8]時間計算量：O(n log n)。毎回半分に分割するため（log nステップ）×各ステップでn回比較 = O(n log n)。これが比較ベースのソートにおける理論上の最適値です。
パフォーマンス比較
| アルゴリズム | 最良 | 平均 | 最悪 | 安定性 | 追加メモリ |
|---|---|---|---|---|---|
| バブルソート | O(n) | O(n²) | O(n²) | 安定 | O(1) |
| 選択ソート | O(n²) | O(n²) | O(n²) | 不安定 | O(1) |
| マージソート | O(n log n) | O(n log n) | O(n log n) | 安定 | O(n) |
- 安定(stable): 同じ値の元の順序が保持されます。（例：点数が同じ生徒の名前順）
- バブル/選択は追加メモリを必要としませんが（インプレース）、マージは新しいリストを作成する必要があります。
10,000個の場合：バブル/選択 ≈ 1億回演算、マージ ≈ 13万回。差が770倍です。
実務ではどのように使うか
# Python内蔵 — Timsort (マージ + 挿入ソートのハイブリッド)numbers = [5, 3, 8, 1, 2]sorted(numbers) # 新しいリストを返すnumbers.sort() # 元のリストをソート
# 基準を指定students = [("김훈", 90), ("이수", 85), ("박진", 95)]sorted(students, key=lambda s: s[1]) # 点数順sorted(students, key=lambda s: s[1], reverse=True) # 降順Pythonのsorted()は、Timsortアルゴリズムを使用します。マージソートと挿入ソートの長所を組み合わせたもので、実際のデータに対して非常に効率的です。直接ソートを実装する必要がない理由です。
重要なまとめ
3つのアルゴリズムは、同じ問題を異なるアプローチで解決し、その違いがO(n²) vs O(n log n)という劇的なパフォーマンスの違いとして現れます。これがアルゴリズムを学ぶ理由です。同じ結果を出すとしても、どのように到達するかによって、1000倍以上の違いが生じます。ソートだけでなく、検索、グラフ、最適化など、すべてのアルゴリズム問題に同じ原則が適用されます。