algorithm - クイックソートアルゴリズムの安定性

Question

クイックソートは、隣接していない要素を交換するため、安定していません。

この声明を理解するのを手伝ってください。

パーティショニングがどのように機能するか、および安定性とは何かを知っています。しかし、これが安定していない理由として、上記の理由がわかりませんか？次に、マージソートについても同じことが言えると思いますが、安定したアルゴリズムであると引用されています。

Answer 1

次のペアの配列の分割中に何が起こるかを考えてみましょう。コンパレータは整数 (のみ) を使用します。文字列はちょうどそこにあるので、2 つの要素は等しいかのように比較できますが、実際には区別できます。

(4, "first"), (2, ""), (3, ""), (4, "second"), (1, "")

定義によれば、並べ替えの後、等しいかのように比較される 2 つの要素 (2 つの s) が前と同じ順序で表示される場合、並べ替えは安定しています。4

3ピボットとして選択するとします。2 つの4要素は、その後1とその2前に配置されます (それよりも少し多くのことがあります。ピボットは既に正しい位置にあるため、ピボットの移動は無視しましたが、パーティショニングを理解していると言います)。

一般に、クイックソートは、パーティションの後に 2 つの s がどこにあるのか特定の保証を与えません4。ほとんどの実装ではそれらが逆になると思います。たとえば、Hoare の従来の分割アルゴリズムを使用すると、配列は次のように分割されます。

(1, ""), (2, ""), (3, ""), (4, "second"), (4, "first")

これはソートの安定性に違反します。

各パーティションは安定していないため、全体的な並べ替えはそうではありません。

Steve314 がコメントで指摘しているように、マージ時に等しい要素に遭遇した場合、マージしている 2 つの半分の「下」から来たものを常に最初に出力する場合、マージソートは安定しています。つまり、各マージは次のように見える必要があります。「左」は、元の配列の下から来る側です。

while (left not empty and right not empty):
    if first_item_on_left <= first_item_on_right:
       move one item from left to output
    else:
       move one item from right to output
move everything from left to output
move everything from right to output

もしそうなら、マージは安定しません<=。<

Answer 2

次のペアの配列を検討してください。

{(4,'first');(2,'');(1,'');(4,'second');(3,'')}

3 をピボットと見なします。クイック ソートの実行中に、配列は次のように変更されます。

1. {(4,'first');(2,'');(1,'');(4,'second');(3,'')}
2. {(2,'');(4,'first');(1,'');(4,'second');(3,'')}
3. {(2,'');(1,'');(4,'first');(4,'second');(3,'')}
4. {(2,'');(1,'');(3,'');(4,'second');(4,'first')}
5. {(1,'');(2,'');(3,'');(4,'second');(4,'first')}

上記から明らかなように、相対的な順序が変更されています。これが、クイックソートが「安定性を保証しない」と言われる理由です。

Answer 3

ユーザーが並べ替えられた配列を持ち、別の列で並べ替えるようになります。並べ替えアルゴリズムは、前の並べ替えキーとは異なるが新しい並べ替えキーで同じ値を持つ要素の相対的な順序を常に保持しますか? そのため、常に要素の順序を保持する (新しいソート キーで変わらない) ソート アルゴリズムは、「安定したソート」と呼ばれます。