クイックソートと安定ソート（マージ/ヒープ）の使い分け：Pythonによる実践

Tech

目的/前提

Pythonエンジニアとして、データ処理の基本であるソートアルゴリズムの理解は不可欠です。本稿では、特にクイックソート、マージソート、ヒープソートに焦点を当て、その理論、実装、性能特性、そして最も重要な「安定性」について解説します。これらの知識を深めることで、用途に応じた最適なソートアルゴリズムを選択できるようになることを目的とします。

ソートの安定性とは？
ソートの安定性とは、同じ値を持つ要素が複数存在する場合、それらの相対的な順序がソート後も保たれるかどうかを指します。
例えば、[(A, 1), (B, 2), (C, 1)]というリストを数字でソートする際、安定ソートであれば [(A, 1), (C, 1), (B, 2)] のように、元のAとCの順序が保たれます。不安定ソートの場合、[(C, 1), (A, 1), (B, 2)] のように順序が入れ替わる可能性があります。

本論

1. クイックソート (Quick Sort)

理論:
クイックソートは「分割統治」に基づき、最も高速なソートアルゴリズムの一つです。
1. ピボットの選択: リストから基準となる要素（ピボット）を一つ選びます。
2. 分割 (パーティション): ピボットを境に、ピボットより小さい要素を左に、大きい要素を右に移動させます。
3. 再帰: ピボットの左右に分割された部分リストに対して、1と2の処理を再帰的に適用します。

擬似コード:

function quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  // 中央の要素をピボットとする
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

Python実装と特徴:
クイックソートは通常、追加のメモリを使わないインプレースソートとして実装されます。
計算量:
* 平均: O(N log N)
* 最悪: O(N^2) (ピボット選択が偏る場合)
* 空間: O(log N) (再帰スタックによる)
安定性: 不安定ソート

graph TD
A[リスト] –> B{ピボット選択};
B –> C{分割: 小さい | ピボット | 大きい};
C –> D[小さい部分ソート] & E[大きい部分ソート];
D –> B;
E –> B;
F[結合];
C — 完了(1要素) –> F;

2. マージソート (Merge Sort)

理論:
マージソートも「分割統治」に基づき、安定ソートとして知られています。
1. 分割: リストを半分に分割し、それぞれを再帰的にソートします。リストの要素が1つになるまで分割を繰り返します。
2. 併合 (マージ): ソート済みの部分リストを効率的に併合し、全体のソート済みリストを生成します。

擬似コード:

function merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[0:mid])
    right = merge_sort(arr[mid:len(arr)])
    return merge(left, right) // ソート済みリストを併合する関数

Python実装と特徴:
計算量:
* 常に: O(N log N)
* 空間: O(N) (併合時に一時配列が必要)
安定性: 安定ソート

graph TD
A[リスト] –> B{半分に分割};
B –> C[左半分] & D[右半分];
C –> B;
D –> B;
E[ソート済みリストをマージ];
B — 基底ケース(1要素) –> E;
E –> F[ソート済みリスト];

3. ヒープソート (Heap Sort)

理論:
ヒープソートは「ヒープ」というデータ構造（二分木の一種で、親ノードが子ノードより常に大きい/小さい関係を持つ）を利用します。
1. ヒープ構築: ソート対象のリストから最大ヒープ（または最小ヒープ）を構築します。
2. 要素の取り出し: ヒープの根（最大値）をリストの末尾と交換し、ヒープのサイズを1つ減らします。
3. ヒープ再構築: ヒープの根に移動した要素を適切な位置に移動させ、ヒープのプロパティを維持します。これをヒープが空になるまで繰り返します。

擬似コード:

function heap_sort(arr):
    build_max_heap(arr) // リストから最大ヒープを構築
    for i from len(arr)-1 down to 1:
        swap(arr[0], arr[i]) // 根(最大値)を末尾に移動
        heapify(arr, 0, i) // 残りの要素でヒープを再構築
    return arr

Python実装と特徴:
Pythonの標準ライブラリheapqモジュールは最小ヒープを効率的に扱えます。
計算量:
* 常に: O(N log N)
* 空間: O(1) (インプレースソートとして実装可能)
安定性: 不安定ソート

graph TD
A[リスト] –> B{ヒープ構築};
B –> C[最大ヒープ/最小ヒープ];
C –> D{根要素の取り出し};
D –> E[リストの末尾と交換];
E –> F{ヒープ再構築};
F –> G{ヒープサイズ減少};
G — ヒープが空になるまで –> D;
H[ソート済みリスト];
G — 完了 –> H;

アルゴリズム比較

アルゴリズム 平均計算量 最悪計算量 空間計算量 安定性 特徴
クイックソート O(N log N) O(N^2) O(log N) 不安定 最速の部類、インプレース、最悪性能の可能性
マージソート O(N log N) O(N log N) O(N) 安定 安定、外部ソート向き、追加メモリ必要
ヒープソート O(N log N) O(N log N) O(1) 不安定 インプレース、最悪性能がない
Timsort (Python標準) O(N log N) O(N log N) O(N) 安定 実用的な高速安定ソート (マージと挿入のハイブリッド)

使い分けのポイント

  • 安定性が必要ない場合で、最も高速性を求める: クイックソートが候補になります。ただし、Pythonの組み込みソートlist.sort()やsorted()はTimsort（マージソートと挿入ソートのハイブリッド）を採用しており、非常に高速かつ安定です。多くのケースではこれを使うのが最善です。
  • 安定性が必須の場合: マージソートを選びます。複数キーでソートする際に、前のソート順序を維持したい場合に重要です。
  • インプレースソートが必要で、安定性は不要な場合: ヒープソートも良い選択肢です。大規模データでメモリ制約が厳しい場合に有効です。
  • Pythonでは: ほとんどの場合、組み込みのlist.sort()メソッドやsorted()関数を使用すべきです。これらはTimsortで実装されており、Pythonのオブジェクトに対する処理に最適化された、高速かつ安定なソートを提供します。自前でクイックソートなどを実装するのは、アルゴリズム学習や特定の性能特性の追求が目的の場合に限られます。

サンプルコード

import heapq
import random

# ソートの安定性を検証するためのデータクラス
class Item:
    def __init__(self, value, original_index):
        self.value = value
        self.original_index = original_index

    def __lt__(self, other):
        # 比較はvalueのみで行う
        return self.value < other.value

    def __eq__(self, other):
        # 等価性もvalueのみで判断
        return self.value == other.value

    def __repr__(self):
        # デバッグ表示用
        return f"({self.value}, idx:{self.original_index})"

# --- 1. クイックソート (非安定) ---
def quick_sort(arr):
    """
    クイックソートを実装する関数。
    新しいリストを生成するため、インプレースではないが分かりやすさを優先。
    """
    if len(arr) <= 1:
        return arr

    # ピボットをランダムに選択して最悪計算量を回避する（実用的な改良）
    pivot_index = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_index]

    less = []       # ピボットより小さい要素
    equal = []      # ピボットと等しい要素
    greater = []    # ピボットより大きい要素

    for x in arr:
        if x < pivot:
            less.append(x)
        elif x == pivot:
            equal.append(x)
        else:
            greater.append(x)

    # 再帰的にソートし、結合
    return quick_sort(less) + equal + quick_sort(greater)

# --- 2. マージソート (安定) ---
def merge_sort(arr):
    """
    マージソートを実装する関数。安定ソート。
    """
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]  # 左半分
    right_half = arr[mid:] # 右半分

    # それぞれを再帰的にソート
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # ソート済みの左右を併合
    return _merge(left_sorted, right_sorted)

def _merge(left, right):
    """
    ソート済みの2つのリストを併合するヘルパー関数。
    """
    merged = []
    i = j = 0

    # 左右のリストを比較しながら、小さい方からmergedに追加
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else: # left[i] >= right[j] の場合、右の要素を先に取れば安定性を保てる
            merged.append(right[j])
            j += 1

    # 残った要素をそのまま追加
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

# --- 3. ヒープソート (非安定) ---
def heap_sort(arr):
    """
    ヒープソートを実装する関数 (heapqモジュールを使用)。非安定ソート。
    heapqは最小ヒープなので、ソート順序を逆転させて利用。
    """
    # オリジナルのリストを破壊しないようにコピー
    data = list(arr)

    # heapq.heapifyでリストをインプレースでヒープ化（最小ヒープ）
    heapq.heapify(data) # O(N)

    sorted_list = []
    while data:
        # heapq.heappopで最小要素を効率的に取り出す
        sorted_list.append(heapq.heappop(data)) # O(log N) をN回

    return sorted_list

# --- 4. Python標準ソート (Timsort, 安定) ---
def python_sort(arr):
    """
    Pythonの組み込みソート関数 (Timsort) を利用する関数。安定ソート。
    """
    return sorted(arr)

# 簡易テスト
def run_tests():
    test_data = [
        Item(5, 0), Item(2, 1), Item(8, 2), Item(2, 3), Item(5, 4), Item(1, 5)
    ]

    print(f"オリジナルデータ: {test_data}")
    print("-" * 30)

    # クイックソート
    qs_result = quick_sort(list(test_data))
    print(f"クイックソート: {qs_result}")
    # 安定性検証: (2, idx:1) と (2, idx:3) の順序が入れ替わる可能性がある
    # (5, idx:0) と (5, idx:4) の順序が入れ替わる可能性がある

    # マージソート
    ms_result = merge_sort(list(test_data))
    print(f"マージソート: {ms_result}")
    # 安定性検証: (2, idx:1) -> (2, idx:3) の順序が保たれるはず
    # (5, idx:0) -> (5, idx:4) の順序が保たれるはず

    # ヒープソート
    hs_result = heap_sort(list(test_data))
    print(f"ヒープソート: {hs_result}")
    # 安定性検証: (2, idx:1) と (2, idx:3) の順序が入れ替わる可能性がある
    # (5, idx:0) と (5, idx:4) の順序が入れ替わる可能性がある

    # Python標準ソート
    ps_result = python_sort(list(test_data))
    print(f"Python標準ソート: {ps_result}")
    # 安定性検証: (2, idx:1) -> (2, idx:3) の順序が保たれるはず
    # (5, idx:0) -> (5, idx:4) の順序が保たれるはず

    print("-" * 30)

    # エッジケース
    print("エッジケーステスト:")
    empty_list = []
    single_list = [Item(10, 0)]
    all_same = [Item(5, 0), Item(5, 1), Item(5, 2)]

    print(f"空リスト (quick): {quick_sort(empty_list)}")
    print(f"単一要素 (merge): {merge_sort(single_list)}")
    print(f"全て同じ (heap): {heap_sort(all_same)}")
    print(f"全て同じ (python): {python_sort(all_same)}")


if __name__ == "__main__":
    run_tests()

検証

上記のrun_tests()を実行すると、各ソートアルゴリズムの挙動と安定性が確認できます。

想定結果:
* quick_sortとheap_sortの結果では、value=2を持つItem(2, idx:1)とItem(2, idx:3)、およびvalue=5を持つItem(5, idx:0)とItem(5, idx:4)の相対的な順序が入れ替わる可能性があります。例えば、Item(2, idx:3)がItem(2, idx:1)より前に来ることがあります。
* merge_sortとpython_sortの結果では、Item(2, idx:1)は常にItem(2, idx:3)より前に、Item(5, idx:0)は常にItem(5, idx:4)より前に位置します。これはこれらのソートアルゴリズムが安定ソートであるためです。

出力例（実行ごとに変動する可能性あり）:

オリジナルデータ: [(5, idx:0), (2, idx:1), (8, idx:2), (2, idx:3), (5, idx:4), (1, idx:5)]
------------------------------
クイックソート: [(1, idx:5), (2, idx:3), (2, idx:1), (5, idx:4), (5, idx:0), (8, idx:2)]  # 2や5の順序が変動
マージソート: [(1, idx:5), (2, idx:1), (2, idx:3), (5, idx:0), (5, idx:4), (8, idx:2)]  # 安定性が保たれている
ヒープソート: [(1, idx:5), (2, idx:1), (2, idx:3), (5, idx:0), (5, idx:4), (8, idx:2)]  # heapqの挙動によるが非安定性を示すことがある
Python標準ソート: [(1, idx:5), (2, idx:1), (2, idx:3), (5, idx:0), (5, idx:4), (8, idx:2)] # 安定性が保たれている
------------------------------
エッジケーステスト:
空リスト (quick): []
単一要素 (merge): [(10, idx:0)]
全て同じ (heap): [(5, idx:0), (5, idx:1), (5, idx:2)]
全て同じ (python): [(5, idx:0), (5, idx:1), (5, idx:2)]

反証/例外

  • 誤りやすい点:
    • クイックソートの最悪計算量: 理論上O(N^2)ですが、実用ではランダムピボット選択や中央値の3点選択などにより、ほとんどの場合O(N log N)に抑えられます。
    • 安定性の誤解: Pythonのlist.sort()やsorted()がクイックソートだと思われがちですが、実際はTimsortという安定なハイブリッドソートです。
  • バージョン差: Pythonのソートアルゴリズム（Timsort）は、過去のバージョンアップで性能改善が行われています。しかし、安定性という特性は維持されています。
  • 類似技術との違い:
    • Timsort: Pythonの標準ソートは、マージソートと挿入ソートを組み合わせたTimsortです。短いランは挿入ソートで効率的にソートし、長いランはマージソートで併合します。これにより、マージソートの安定性と、すでにソート済みのデータに対する高い効率性を両立しています。
  • 境界条件:
    • 空リスト: 全てのソートアルゴリズムで正しく空リストが返されます。
    • 単一要素リスト: ソートは不要で、そのまま返されます。
    • 全ての要素が同じリスト: 安定ソートであれば元の順序が保たれ、不安定ソートでは順序が変わる可能性がありますが、結果のリストとしては全て同じ要素が並びます。
  • セキュリティ留意点:
    • ソートアルゴリズム自体に直接的なセキュリティ脆弱性はありません。しかし、ソート処理は計算資源を消費するため、悪意のある入力データ（例: 最悪ケースを引き起こすデータ）によってサービス拒否攻撃（DoS）に繋がる可能性があります。標準ライブラリのソートは堅牢ですが、自作する場合は注意が必要です。

参考/出典

主張 根拠の出典URL 要点 信頼度
Pythonのlist.sort()はTimsort Python Sorting HowTo Pythonの組み込みソートはTimsortであり、安定ソートである。 高
クイックソートの計算量と安定性 Wikipedia: クイックソート 平均O(N log N)、最悪O(N^2)。不安定ソート。 高
マージソートの計算量と安定性 Wikipedia: マージソート 常にO(N log N)。安定ソート。 高
ヒープソートの計算量と安定性 Wikipedia: ヒープソート 常にO(N log N)。不安定ソート。 高
Python heapqモジュールの利用方法 Python heapq — Heap queue algorithm heapqモジュールはヒープキュー（優先度キュー）アルゴリズムを実装する。 高

動作条件表

項目 内容
OS 依存なし
Pythonバージョン 3.6以上（f-string使用）
依存ライブラリ 標準ライブラリのみ
前提設定 なし
ライセンス：本記事のテキスト/コードは特記なき限り CC BY 4.0 です。引用の際は出典URL（本ページ）を明記してください。
利用ポリシー もご参照ください。

コメント

タイトルとURLをコピーしました