最悪の場合、クイックソート再帰の深さにはO(n)のスタックスペースが必要です。最悪の場合、大きなセットでスタックオーバーフローが発生しないのはなぜですか?(逆順)
3 に答える
ピボットの両側で再帰すると、最悪の場合、十分に大きなデータに対してスタックオーバーフローが発生します。そのため、本番コードで単純なQuickSortを使用する人は誰もいません。
Omega(n)
最悪の場合のスタックの使用を防ぐために、アルゴリズムに簡単な変更を加えることができます。各パーティションの後で、「小さい半分」を再帰的にクイックソートしてから、繰り返しループして「大きい半分」を実行します。これにはO(log n)
、追加のスタックスペースが必要です。必要に応じて、これを再度変更することで、O(1)
スタックスペースとO(log n)
追加の非スタックスペースにすることができます。「ビッグハーフ」を事前に割り当てられた配列(または選択した他の後入れ先出しデータ構造)の最後にプッシュし、ループして「スモールハーフ」を実行し、下を押すと最後をポップします次に行うデータ構造から要素を削除します。
Omega(n^2)
最悪の場合の実行時間を回避するために、さらに変更を加えることができます。しかし、それはもはや単純なQuickSortではなく、QuickSort-with-median-of-medians-pivot-selection、またはIntrosortなどです。
次に、最悪の場合、順序の大きいデータセットに対してスタックオーバーフローが発生しない理由
します。なぜそうではないと思いますか?
(ただし、クイックソートの最悪の場合の入力は、選択したピボットによって異なります。通常、逆のシーケンスではありません。実際、ピボットの単純な選択の場合、別の最悪の場合の入力は、すでにソートされているシーケンスであり、逆になります。)
しかし、ソートアルゴリズムのライブラリ実装が実際にクイックソートされることは、まさにこの理由から、今日ではめったにありません。たとえば、C ++は代わりにイントロソートstd::sort
を使用します。これは修正されたクイックソートであり、繰り返しが深くなりすぎるとすぐに別のソートアルゴリズムに切り替わります。
逆のシーケンスの場合(最悪の場合)、スタックオーバーフローが発生する可能性があります。配列が内部関数スタックに対して大きすぎる可能性があるためです。(たとえば、99,000,000要素)再帰をstack
データ構造に置き換えることができます。ループしますwhile (stck.empty() == false)
function quicksort(arr[0,1,...n-1])
stack.push(pair(0, n - 1))
while stack not empty
interval = stack.pop()
...
...
stack.push(interval(0, pivot - 1))
stack.push(interval(pivot + 1, n - 1))