[解決済み] この奇妙なソートアルゴリズムは何ですか？

質問

いくつかの 答え は元々このようなソートアルゴリズムを持っていました。

for i from 0 to n-1:
    for j from 0 to n-1:
        if A[j] > A[i]:
            swap A[i] and A[j]

ただし i と j はフルレンジになるため j よりも大きくも小さくもなり得ます。 i というように、正しい順序と間違った順序の両方のペアを作ることができます（そして、実際に は は両方やる！）。私はこれは間違いだと思い（作者も後でそう言っています）、これでは配列が混乱してしまうと思ったのですが、正しくソートされているようです。理由は明らかではありませんが。しかし のコード のシンプルさ（フルレンジ化、そしてノー +1 バブルソートのようにを使わない)ため、興味深いものとなっています。

それは正しいのですか？もしそうなら、なぜそれが機能するのですか？また、名前はあるのでしょうか？

テストを伴うPythonの実装です。

from random import shuffle

for _ in range(3):
    n = 20
    A = list(range(n))
    shuffle(A)
    print('before:', A)

    for i in range(n):
        for j in range(n):
            if A[j] > A[i]:
                A[i], A[j] = A[j], A[i]

    print('after: ', A, '\n')

出力例 ( オンラインでお試しください ):

before: [9, 14, 8, 12, 16, 19, 2, 1, 10, 11, 18, 4, 15, 3, 6, 17, 7, 0, 5, 13]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

before: [5, 1, 18, 10, 19, 14, 17, 7, 12, 16, 2, 0, 6, 8, 9, 11, 4, 3, 15, 13]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

before: [11, 15, 7, 14, 0, 2, 9, 4, 13, 17, 8, 10, 1, 12, 6, 16, 18, 3, 5, 19]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

編集：ある人が、とても素晴らしい新品の 紙 を指摘されました。はっきり言って、私たちは無関係であり、偶然の一致です。私が知る限りでは、それは 提出された に投稿されました。 以前 私の質問のきっかけとなったその答えと を公開しました。 arXivによる の後に 私の質問です。

どのように解決するのですか？

正しいことを証明するには、ある種の不変量を見つける必要があります。ループのすべてのパスの間に真である何か。

見てみると、内側のループの一番最初のパスの後に 最大の の要素は、実際には になります。 の位置になります。

さて、内部ループの2回目のパスで i = 1 となっており、最初の比較は i = 1 と j = 0 . つまり、最大の要素が位置0にあったのですが、この比較の後、位置1に入れ替わることになります。

一般に、外側のループの各ステップの後、最大の要素が右に1つ移動していることを見るのは難しくありません。したがって、全ステップの後、少なくとも最大の要素が正しい位置にあることがわかります。

残りの要素についてはどうでしょうか。2番目に大きい要素が、位置 i の位置にあるとします。私たちは 最大の 要素の位置は i-1 のようになります。カウンター j は 0 から始まります。そこで今度は、最初の A[j] であるような最初の A[j] > A[i] . さて、その A[i] は 2 番目に大きな要素なので、最初にそうなるのは j = i-1 は1番目に大きな要素で、です。このように、隣接しているのに入れ替わってしまい、"right"の順番になっています。では A[i] は再び最大の要素を指すようになり、したがって内部ループの残りの部分ではこれ以上スワップが行われることはありません。

というわけで、こう言えます。外側ループのインデックスが2番目に大きい要素の位置を超えたら、2番目と1番目の要素は正しい順序になります。外側のループのすべての反復で、彼らは今、一緒にスライドアップするので、我々は、アルゴリズムの最後に、第1および第2最大の要素の両方が正しい位置にあることを知っています。

3番目に大きい要素についてはどうでしょうか。これもまた、同じロジックを使うことができます。外側のループのカウンタ i が 3 番目に大きい要素の位置に来たら、2 番目に大きい要素のすぐ下に来るように（すでに見つけていた場合は！）、または 1 番目に大きい要素のすぐ下に来るように入れ替えられます。

ああ。そして、ここで私たちは不変量を手に入れました。後に k の繰り返しの後、k-length の要素のシーケンスは、位置 k-1 で終わる要素の列はソートされた順序になる。

1回目の反復の後、位置0にある1長の配列は正しい順序になります。これは些細なことです。

2回目の反復の後、最大の要素は位置1にあることが分かっているので、明らかに配列は A[0] , A[1] は正しい順序です。

では、ステップにある k であるとすると、位置 k-1 という順番になります。では i = k を繰り返し、その上に j . これは基本的に、新しい要素が適切にソートされるように、既存のソートされたシーケンスに挿入される必要がある位置を見つけることです。一旦これが起こると、残りの要素は "一つ上にバブルします" 現在、最大の要素は位置 i = k となり、それ以上の入れ替わりは起こりません。

こうして最後にステップの終わりで N までの全ての要素は N-1 までが正しい順序であることを示します。