algorithm - クイックソート-どのサブパートを最初にソートする必要がありますか？

Question

私は、2つの再帰的なクイックソート呼び出しの順序に関してこれを主張するいくつかのテキストを読んでいます：

...最初に小さいサブ問題を呼び出すことが重要です。これを末尾再帰と組み合わせて使用​​すると、スタックの深さがlognになります。

それが何を意味するのかまったくわかりませんが、なぜ最初に小さいサブアレイでクイックソートを呼び出す必要があるのですか？

Answer 1

暗黙の二分木としてクイックソートを見てください。ピボットがルートで、左右のサブツリーが作成するパーティションです。

次に、このツリーの深さ優先検索を行うことを検討してください。再帰呼び出しは、実際には、上記の暗黙的なツリーで深さ優先検索を実行することに対応しています。また、ツリーには常に小さい方のサブツリーが左側の子としてあると仮定するため、実際にはこのツリーで予約注文を行うことをお勧めします。

ここで、スタックを使用して事前注文を実装するとします。この場合、左側の子のみをプッシュし (ただし、親はスタックに保持します)、右側の子をプッシュするときが来たら (ノードにそのノードがあるかどうかを知っている状態を維持したとします)左の子が探索されているかどうかに関係なく)、右の子をプッシュする代わりに、スタックの一番上を置き換えます (これは末尾の再帰部分に対応します)。

最大スタック深さは、最大の「左の深さ」です。つまり、左の子に向かう各エッジを 1 としてマークし、右の子に向かう各エッジを 0 としてマークすると、エッジの合計が最大のパスが表示されます (基本的には、右端は数えないでください)。

左のサブツリーには要素が半分しかないため、左に移動するたびに (つまり、トラバースしてエッジに 1 をマークする)、探索する残りのノードの数を少なくとも半分に減らします。

したがって、表示される 1 とマークされたエッジの最大数は log n 以下です。

したがって、常により小さいパーティションを選択し、末尾再帰を使用する場合、スタック使用量は log n を超えません。

Answer 2

一部の言語には末尾再帰があります。これは、f(x) { ... ... .. ... .. g(x)} と書くと、g(x) への最後の呼び出しが関数呼び出しでまったく実装されないことを意味します。 、ただしジャンプを使用するため、最後の呼び出しでスタック スペースが使用されません。

クイックソートは、ソートするデータを 2 つのセクションに分割します。短い方のセクションを常に最初に処理すると、スタック領域を消費する各呼び出しには、それを呼び出した再帰呼び出しのサイズのせいぜい半分のデータのセクションがソートされます。したがって、ソートする要素が 10 個ある場合、スタックの最深部には、それらの 10 個の要素をソートする呼び出しがあり、次に最大で 5 つの要素をソートする呼び出しがあり、次に最大で 2 つの要素をソートする呼び出しがあり、次にソートする呼び出しがあります。最大で 1 要素 - 10 要素の場合、スタックはこれ以上深くはなりません - スタック サイズはデータ サイズのログによって制限されます。

これを気にしなければ、10 個の要素を並べ替える呼び出し、次に 9 個の要素を並べ替える呼び出し、8 個の要素を並べ替える呼び出しというように、スタックが深くなる可能性があります。ソートする要素の数として。しかし、短いセクションを最初にソートする場合、これは末尾再帰では発生しません。10 個の要素を 1 個の要素と 9 個の要素に分割することはできますが、9 個の要素をソートする呼び出しは最後に行われ、ジャンプとして実装されるためです。これ以上スタック領域を使用しない - 呼び出し元が以前に使用していたスタック領域を再利用します。

Answer 3

理想的には、リストはほぼ同じサイズの 2 つのサブリストに分割されます。どのサブリストを最初に処理するかは問題ではありません。

しかし、悪い日にリストが可能な限り偏った方法で分割された場合、2 つまたは 3 つの項目、おそらく 4 つの項目のサブリストと、元の項目とほぼ同じ長さのサブリストになります。これは、パーティション値の選択が不適切であるか、データが巧妙に作成されていることが原因である可能性があります。最初に大きなサブリストに取り組んだらどうなるか想像してみてください。Quicksort の最初の呼び出しは、短いリストのポインター/インデックスをスタック フレームに保持し、長いリストのクイックソートを再帰的に呼び出します。これも非常に短いリストと長いリストにひどく分割され、最初に長いサブリストを実行し、繰り返します...

最終的に、最悪の最悪の日に、最悪のデータが発生すると、元のリストの長さに比例した数のスタック フレームが構築されます。これはクイックソートの最悪の場合の動作であり、O(n) の再帰呼び出しの深さです。(パフォーマンスではなく、クイックソートの再帰の深さについて話していることに注意してください。)

最初に短いサブリストを実行すると、かなり早く削除されます。元のリストの長さに比例して、まだ多数の小さなリストを処理していますが、それぞれが 1 回または 2 回の浅い再帰呼び出しによって処理されます。引き続き O(n) 呼び出し (パフォーマンス) を行いますが、それぞれの深さは O(1) です。