バブルアルゴリズムよりも単純なソートアルゴリズム：バグだらけに見えるプログラムが実は正しい

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載しています。転載の際は出典元にご連絡ください。

[[427437]]

プログラムのバグも正の数になることがありますか?

本当に効きますよ。

たとえば、プログラマーがよく知っているソートアルゴリズムは、2 つの「バグ」のおかげで実際には正常に動作することがあり、これは本当に驚くべきことです。

このプログラマーが配列を昇順に並べ替えるために書いたコードを見てみましょう。

 i = 1からnまで
j = 1からnまでの場合
A[i] < A[j]ならば
A[i]とA[j]を入れ替える

今日、この一連のコードは Hacker News フォーラムで突然人気となり、多くのプログラマーの注目を集めています。

このコードを一目見たときのあなたの反応はどのようなものでしょうか?このプログラマーは基本的なバブリングアルゴリズムを書くのが下手すぎると思いますか?

不等号の方向が間違っており、第2層ループインデックスjの範囲も間違っています。

つまり、このコードは「正しいはずがない」ということです。

△ バブルアルゴリズム

しかし、実際に実行すると、結果が確かに昇順に並べられていることがわかります。

正しいバブリング アルゴリズム コードを見てみましょう。

 i = 1からnまで
j = i + 1から nまで
A[i] > A[j]の場合
A[i]とA[j]を入れ替える

後者の違いは、 j = i + 1 と A[i] > A[j] であり、2つのプログラムは非常に異なります。

しかし、信じられない事実をお伝えしたいと思います。実は、コードの最初の文字列は正しく、厳密に証明できるのです。

では、正しいソートはどのようにして実現されるのでしょうか?

なぜ偶然に的を射ることができるのでしょうか?

よく考えてみると、実はとても簡単に理解できます。このアルゴリズムはバブルソートの半分のスワップ操作しかないため、降順を昇順にプログラムするだけで済みます。

しかし、著者は依然として厳密な証明を示しています。

Pᵢをi(1≤i≤n)回の外側のループの後に得られる配列として定義します。

アルゴリズムが正しければ、最初のi個の項目はすでに昇順になっています。つまり、A[1] ≤ A[2] ≤ . . . ≤ A[i]です。

アルゴリズムが正しいことを証明することは、実際には任意の n に対して Pₙ が成り立つことを証明することです。

数学的帰納法によれば、P₁ が成り立つことを証明し、Pᵢ が成り立つと仮定し、次に Pi+1 も成り立つことを証明するだけで、命題を証明できます。

P₁ は明らかに正しく、このステップは降順の通常のバブリング アルゴリズムと変わりません。最初の外側のループの後、A[1] は配列全体で最大の要素になります。

次に、Pᵢが成り立つと仮定し、Pi+1が成り立つことを証明します。

まず序数kを定義します。

まず、A[k]（kは1からiまで）がA[k]>A[i+1]を満たす最小の数であると仮定すると、A[k−1]≤A[i+1]（k≠1）となります。

A[i+1]≥A[i]の場合、そのようなkは存在しないので、k=i+1と設定します。

次の 3 つのシナリオを考えてみましょう。

1, 1≤j≤k−1 である。

A[i+1]＞A[j]なので要素の交換は発生しません。

2. k ≤ j ≤ i (k=i+1 の場合、このステップは存在しない)

A[j]>A[i+1]なので、比較のたびに要素が交換されます。

スワップの前後の要素を表すためにA[ ]とA′[ ]を使用するので、

A′[i+1] = A[k]、A′[k]=A[i+1]

一連の交換の後、最終的に最大の要素が位置A[i+1]に配置されます。元のA[i+1]が最大の要素になり、元のA[k]とA[k-1]の間のサイズの要素がA[k]に挿入されます。

3. i+1 ≤ j ≤ n

最大の要素が最初の i+1 個の要素と交換されているため、このプロセスでは要素は交換されません。

最後に、Pₙ は昇順ソートアルゴリズムが実行された後の結果です。

ループの内側セットと外側セットの間に範囲の違いがないため、これは「最も単純な」ソート アルゴリズムであると言えます。

コードの観点から見ると、バブルアルゴリズムのように見えますが、証明プロセスから見ると、これは実際には挿入アルゴリズムであることがわかります。

挿入アルゴリズム

アルゴリズムの複雑さ

明らかに、このアルゴリズムは常にn² 回の比較を行うので、アルゴリズム内の交換回数を計算してみましょう。

交換回数は最大でI+2(n-1)回、最小でn-1回であることが証明できます。

Iは最初の数の逆数であり、最大値はn(n-1)/2である。

したがって、アルゴリズム全体の複雑さはO(n²)です。

証明プロセスから、i=1 のループを除いて、他のループの j=i-1 以降の部分は完全に無効であることがわかります。そのため、この部分を省略して簡略化されたアルゴリズムを取得できます。

 i = 2からnまで
j = 1から i − 1まで
A[i] < A[j]ならば
A[i]とA[j]を入れ替える

このアルゴリズムは比較と交換の回数を削減しますが、アルゴリズムの複雑さは依然として O(n²) です。

ネットユーザー：このアルゴリズムは以前にも見たことがある

最も理解しやすいバブルアルゴリズムよりもさらにシンプルなこのソートアルゴリズムは、Hacker News のネットユーザーの注目を集めました。

多くの人が「とても見覚えがある」と思うでしょう。

あるネットユーザーは、オリンピックの数学競技でクラスメートが非常に奇妙なソートアルゴリズムを使用しているのを見たと話した。そのアルゴリズムは機能していたが、非常に非効率的で、挿入ソートに似ていた。

私の記憶が正しければ、これが彼が使用したアルゴリズムです。

実際、このアルゴリズムに関する議論は長い間続いており、2014年から投稿されてきました。今回、著者が論文をarXivにアップロードした後、再び広範囲にわたる白熱した議論が巻き起こりました。

ウーロン事件もありました。

あるネットユーザーは論文をちらっと見て、このアルゴリズムは10年前に自分が提案したものと同じだと思った。

コメントを残すためのアルゴリズム:

一見すると、2 つのアルゴリズムのコードは非常に似ており、原理も多少似ています。

これらはすべてバブルソートのように見えますが、実際には選択ソートに近いものです。

しかし、すぐに誰かが真実を指摘しました。このアルゴリズムでは、j = i + 1〜nであり、A [i] > A [j]のときにスワップが発生します。

著者が提案したアルゴリズムでは、j=1～nのとき、A[i] < A[j]が入れ替わります。

2 つのアルゴリズムを比較すると、ネットユーザーが以前に提案したアルゴリズムの方が、なぜ機能するのか理解しやすいです。

もちろん、本題から外れる人もいます。プログラミングを初めて学んだときにこのアルゴリズムを書いたと冗談を言う人もいました。

私がこれを書いたのは、プログラミングを学び始めたばかりで、何かをソートする最短の方法を見つけたいと思っていたときだったと 100% 確信しています。

しかし、実際のアプリケーションでは、このアルゴリズムの計算には時間がかかりすぎます。

このアルゴリズムはこれまで何度も発見されてきたが、その人たちにはそれを使用する意図はなかったと考える人もいます。

この分類は睡眠分類ほど単純ではないと指摘する人もいました。

スリープ ソートは、n 個のスレッドを構築し、スレッドをソートされた n 個の数値に対応させるというものです。

たとえば、[4,2,3,5,9]のような数字のセットの場合、5つのスレッドが作成され、各スレッドは4秒、2秒、3秒、5秒、9秒スリープします。これらのスレッドが起動すると、対応する番号を報告するだけです。このようにして、すべてのスレッドが起動すると、ソートが完了します。

しかし、著者が提案したアルゴリズムと同様に、スリープソートもマルチスレッドの問題により実装が困難です。

さらに、このネットユーザーは、次のようなアルゴリズムも見たことがあると述べています。

このアルゴリズムは以前に見たことがあるはずですが、名前はないのでしょうか?

すぐに誰かがこう提案した。

名前がない場合は、「面接選別」と呼ぶことをお勧めします。