【Python】クイックソート

概要

クイックソートは、高速かつ効率的なソートアルゴリズムの一つで、分割統治法（Divide and Conquer）に基づいています。クイックソートは、リストをピボットを基準に小さな部分に分けていき、それぞれの部分を再帰的にソートすることで、全体のリストを整列させます。
平均計算量は O(n log n)であり、大規模なデータセットにも適しています。最悪の場合は O(n^2) になりますが、通常の使用では非常に高速です。

クイックソートは、以下の手順で動作します：

1. 配列の中から基準となるピボットを選びます
2. ピボットより小さい要素と大きい要素に配列を分けます
3. 各部分配列に対して再帰的にクイックソートを適用します

この記事では、Pythonでのクイックソート実装方法について説明します。

コード

以下がPythonでのクイックソートの実装例です。

def partition(arr, low, high):
    # 小さい要素のインデックスを管理
    i = low - 1
    # ピボットを最後の要素に設定
    pivot = arr[high]
    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


def quick_sort(arr):
    def _quick_sort(arr, low, high):
        if low < high:
            # パーティション実行
            partition_index = partition(arr, low, high)
            # 左側を再帰的にソート
            _quick_sort(arr, low, partition_index - 1)
            # 右側を再帰的にソート
            _quick_sort(arr, partition_index + 1, high)

    # リスト全体に対してクイックソートを実行
    _quick_sort(arr, 0, len(arr) - 1)
    return arr


# サンプルの使用例
if __name__ == "__main__":
    sample_data = [10, 7, 8, 9, 1, 5]
    print("ソート前:", sample_data)
    sorted_data = quick_sort(sample_data)
    print("ソート後:", sorted_data)

実行結果

上記のコードを実行すると、次のような結果が得られます。

ソート前: [3, 6, 8, 10, 1, 2, 1]
ソート後: [1, 1, 2, 3, 6, 8, 10]

詳細

partition関数は、リストの最後の要素をピボットとして選択し、それを基準にリストを2つの部分に分割します。ピボットより小さい要素は左側、大きい要素は右側に配置されます。
_quick_sort関数は、partition関数によって分割された部分配列を再帰的にソートします。

参考