Python クイックソートアルゴリズムガイド

Python のクイックソートアルゴリズムを調べてください。このインタラクティブなコーディング例では、ピボットの選択、分割、再帰について学びます。

概要

クイックソートは、非常に高速で広く使用されている並べ替えアルゴリズムです。マージソートと同様に、分割統治アプローチを採用します。ただし、クイックソートは要素を「その場で」並べ替えるため、メモリ効率が高くなります。

このアルゴリズムは、リストから「ピボット」要素を選択することで機能します。次に、他の要素を 2 つのサブ配列 (ピボットより小さいものとピボットより大きいもの) に分割します。このプロセスはサブ配列に再帰的に適用されます。

クイックソートの最悪の場合の複雑さは O(n²) ですが、平均実行時間は O(n log n) であり、キャッシュミスが少なく、一時配列作成のオーバーヘッドがゼロであるため、実際には通常、マージソートよりも優れたパフォーマンスを発揮します。

コードと実行の出力

可読性の高いリスト内包表記を使用した簡潔な再帰クイックソートスクリプト。

quicksort.py

エディターで試してみる

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quicksort(left) + middle + quicksort(right)

# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List:  ", sorted_data)

端子出力

Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List:   [1, 3, 4, 5, 6, 7, 12, 15]

段階的な実装

メモリ使用量を最小限に抑える必要があるシステムの並べ替えルーチン
標準言語ライブラリフレームワークでの汎用ソート
分割メカニズムと再帰的分割統治の学術教育

よくある質問

クイックソートで O(n²) の最悪の場合の複雑さを回避するにはどうすればよいでしょうか?

最悪のケースは、選択したピボットが繰り返し最小または最大の要素である場合に発生します。これを軽減するために、開発者はランダムなピボットや「3 つの中央値」値を選択するなどの戦略を使用します。

クイックソートは安定していますか?

いいえ、標準のクイックソートは不安定です。パーティショニング中、要素は長い範囲にわたって交換されるため、重複要素の相対的な順序が変更される可能性があります。

Python クイックソート アルゴリズム ガイド

概要