信じられないほど単純なのに、なぜかソートできるアルゴリズム
I Can't Believe It Can Sort
「I Can't Believe It Can Sort」は、一見ソートできるとは思えないほど単純な擬似コードながら、実際に配列をソートする驚きのアルゴリズム。Stanley P. Y. Fungの論文で紹介されたもので、二重ループで全要素を比較・交換するだけ。計算量はO(n^2)で効率は悪いが、その意外な動作が話題を呼んでいる。
擬似コードを見ただけでは、本当にソートできるとは思えない。しかし、実際にソートしてしまうのだ。
HNでの議論
55- Someone
これについて、なぜ/どうやって動作するかの証明を含む論文があります: https://arxiv.org/pdf/2110.01111。そこにはこう書かれています:
「このアルゴリズムには良いところが何もない。遅い – 最悪ケース、平均ケース、最良ケースのいずれであっても、明らかにΘ(n2)時間で動作する。不必要にすべての位置のペアを2回比較する(ただし第3節を参照)。その背後には直感が何もないように思われ、正しさも完全に明らかではない。学生にソートアルゴリズムを紹介する最初の例として使うべきでは決してない。安定ではなく、外部ソートにはうまく機能せず、オンラインで到着する入力をソートできず、部分的にソートされた入力から利益を得ることもない。その唯一の魅力は、コードの行数と2つのループの「対称性」という点での単純さかもしれない。」
- petercooper
楽しい小さなソートアルゴリズムの話題で言えば、私はいつも「sleep sort」に心をくすぐられていました:
a=[5,3,1,4,2];b=[];a.map(n=>setTimeout(()=>b.push(n),n))
明らかに実際にこれを使うべきではありませんが、このアルゴリズムの動作や落とし穴をさまざまな言語で考えるのは楽しいと思いました。
- senfiaj
最適化されていない挿入ソートのように見えます。
最初のネストされたループの実行後、A[1]は最大値を持ちます。
2回目のネストされたループの実行後、A[1]は常にA[2]と交換されます(等しい場合を除きますが、論理的には何も変わりません)。A[2]は今、最大値を含んでいます。
k回目(k >= 2)のネストされたループの実行後、注意深く見ると、k番目の要素は最初のk-1個のソートされた要素に挿入されます。j >= iのとき、A[k]は最大値を含むため、それ以上何もできません。
k回目(k >= 2)のネストされたループの実行後、最初のk個の要素は互いに相対的にソートされます。最初のネストされたループは最大要素をA[1]に持ってくるという点で特別であり、連続するループは単にA[k]を配列の先頭からソートされた最初のk-1個の要素に挿入しているだけです。
- fwlr
(直感的に)動作しないはずの理由は2つあります。1つは、内側のforループも先頭から始まり、外側のforループがどこにあるかをチェックしないため、`compare(a[0], a[2]) == true`が得られる一方で、`compare(a[2], a[0]) == false`も得られることです。したがって、`compare`の結果から有用な意味を何も得られないように見えます。もう1つは、比較の符号が逆になっていることです。
しかしどういうわけか、動作しないはずのこれら2つの理由が、正確に互いを打ち消し合うように相互作用し、動作するソートを生み出しています!
- edflsafoiewq