小さなサブファイルのうち大きい方をスタックに置くというポリシーにより、スタック上の各エントリがその下のエントリのサイズの半分以下になることが保証されます。
それは完全に真実ではありません。100 要素の配列を並べ替えたいと考えて、最初のピボットが真ん中に来るとします。次に、スタックがあります
49
50
次に、49 要素のパーツをスタックからポップし、分割して、2 つのパーツをスタックにプッシュします。今回はピボットの選択があまり良くなかったとしましょう。ピボットよりも大きくない 20 個の要素がありました。次に、スタックを取得します
20
28
50
各スタック エントリは、下のエントリの半分以上です。
しかし、それは永遠に続くことはできません。
並べ替え全体で、スタック レベルkが占有されている場合、そのサイズは最大でtotal_size / (2^k)です。
並べ替えが始まると、これは明らかに当てはまります。スタックにはレベル 0 の要素が 1 つしかないためです。これは size の配列全体ですtotal_size。
ここで、指定されたプロパティがループに入ったときに保持されると仮定します ( while(!stack.empty()))。
length の部分配列がsスタック レベルからポップされますm。の場合s <= 1、次のループ反復の前に他に何も行われず、不変式が保持され続けます。それ以外の場合、 if 、それを分割した後、2 つの新しいサブ配列が要素と共にs >= 2スタックにプッシュされます。s-1これら 2 つのうち小さい方には sizesmaller_size <= (s-1)/2があり、大きい方には size がありますlarger_size <= s-1。スタック レベルmは 2 つのうち大きい方によって占有されます。
larger_size <= s-1 < s <= total_size / (2^m)
smaller_size <= (s-1)/2 < s/2 <= total_size / (2^(m+1))
スタックレベルのm場合。m+1ループ本体の最後。不変式は次の反復まで保持されます。
lg total_size + 1サイズ 0 のサブ配列は最大でも 1 つスタック上にあるため (次の反復ですぐに取り出されます)、占有されるスタック レベルを超えることはありません。
それにかんする
著者は、「再帰の削除がなければ、スタック サイズがクイックソート用に小さくなることを保証できません」とはどういう意味ですか?
再帰的な実装では、深い再帰を行うことができ、スタック フレームがエンド コールに再利用されない場合、線形スタック スペースが必要になる場合があります。常に最初の要素をピボットとして選択し、既にソートされた配列を選択する愚かなピボット選択を考えてみましょう。
[0,1,2,3,4]
パーティション、ピボットは位置 0 になり、小さい方のサブ配列は空になります。より大きな subarray の再帰呼び出しにより[1,2,3,4]、新しいスタック フレームが割り当てられます (したがって、2 つのスタック フレームが存在します)。同じ原理で、サブ配列を使用した次の再帰呼び出しで[2,3,4]3 番目のスタック フレームが割り当てられます。
再帰終了の削除がある場合、つまりスタック フレームが再利用される場合、上記の手動スタックと同じ保証があります。