クイックソートはどのように機能し、最悪ケースは何ですか？

Question

Accepted Answer

**Quicksort** は分割統治ソートで、**pivot** を選択し、要素をそれより小さいものと大きいものに分割してから、各側を再帰的にソートします。平均 **O(n log n)**、最悪ケース **O(n²)**。 ## アイデア分割により pivot は最終的なソート済み位置に配置されます。左側のすべては小さく、右側のすべては大きいです。両側で再帰します。 ## 例 ```python def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] # pick a pivot left = [x for x in arr if x < pivot] # smaller mid = [x for x in arr if x == pivot] # equal right = [x for x in arr if x > pivot] # larger return quicksort(left) + mid + quicksort(right) quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8] ``` （実際には、メモリを節約するためにインプレース分割が使用されます。） ## 複雑性 | ケース | 時間 | 理由 | |--------|------|------| | 最良/平均 | O(n log n) | バランスの取れた分割 | | 最悪 | O(n²) | 既にソート済みで不適切な pivot | インプレースクイックソートは O(log n) のスタック空間を使用します。 ## 使用時期 / 落とし穴通常、キャッシュフレンドリーで低いオーバーヘッドのため **実践では最速** で、インプレースです。O(n²) 最悪ケースは **ランダム化** または中央値3択 pivot で回避されます。**安定ではありません**。 ## なぜ重要なのかクイックソートは、優れた平均ケース速度と低いメモリ使用量のため、多くの標準ライブラリのデフォルトです。 pivot の選択がなぜ O(n²) 最悪ケースを引き起こすかを理解することは、重要な教訓を教えます：平均ケースと最悪ケースは大きく異なる可能性があります。まさにその微妙さのため、インタビューの好まれるトピックです。

ケース	時間	理由
最良/平均	O(n log n)	バランスの取れた分割
最悪	O(n²)	既にソート済みで不適切な pivot