信じられないソートアルゴリズム "ICan'tBelieveItCanSort"

TL;DR

なんとこのシンプル極まりないコードでソートが実現できます。

for i in range(len(A)):
    for j in range(len(A)):
        if A[i] < A[j]:
            A[i], A[j] = A[j], A[i]

説明

2021 年 10 月 3 日、みんな大好き arXiv にこんな論文が投稿されました。

今までで一番簡単で一番驚きのソートアルゴリズムを見つけたそうです。それ（を Python で書いたもの）が先ほどもお見せしたこちらです。

# ICan'tBelieveItCanSort
for i in range(len(A)):
    for j in range(len(A)):
        if A[i] < A[j]:
            A[i], A[j] = A[j], A[i]

非常に単純な二重ループの中で要素をスワップしているだけです。ちょっと他のソートアルゴリズムとも見比べてみましょう。

# バブルソート
for i in range(len(A)):
    for j in range(len(A) - i - 1):
        if A[j] > A[j + 1]:
            A[j], A[j + 1] = A[j + 1], A[j]

# 選択ソート
for i in range(len(A) - 1):
    minimum_value_index = i
    for j in range(i + 1, len(A)):
        if A[minimum_value_index] > A[j]:
            minimum_value_index = j
    A[i], A[minimum_value_index] = A[minimum_value_index], A[i]

# 挿入ソート
for i in range(len(A)):
    picked = A[i]
    j = i - 1
    while j >= 0 and picked < A[j]:
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = picked

どれも有名な初歩的ソートアルゴリズムですが、こうして見比べてみると ICan'tBelieveItCanSort アルゴリズムがいかにシンプルかお判りいただけると思います。

ほんとにソートできてる？

ほんとにあんなコードでソートできるのかお疑いの方もいるでしょう。特に、ICan'tBelieveItCanSort アルゴリズムのコードにはひとつ不審な点があります。

for i in range(len(A)):
    for j in range(len(A)):
        if A[i] < A[j]: # ← ここ
            A[i], A[j] = A[j], A[i]

このコードを見た時に多くの人が思うのが、「よしんばソートできたとして、これ降順ソートになるんじゃねえのか？」​ということです。ところが実際に試してみるときちんと昇順ソートになります。このアルゴリズムを詳しく検証してみるとしましょう。

ここから先、説明を単純化するため A の要素には重複はないものとします。ただし A の要素に重複がある一般の場合でもほぼ同様の議論でアルゴリズムの正当性は示せます。

天下り的なやりかたで恐縮ですが、まずは i == 0 のループを分離します。するとこうなります。

for j in range(len(A)):
    if A[0] < A[j]:
        A[0], A[j] = A[j], A[0]

for i in range(1, len(A)):
    for j in range(len(A)):
        if A[i] < A[j]:
            A[i], A[j] = A[j], A[i]

分離したループをよく見てみましょう。

for j in range(len(A)):
    if A[0] < A[j]:
        A[0], A[j] = A[j], A[0]

A のすべての要素を走査し、A[0] より大きければ A[0] と交換します。すなわち、このループは A の最大値を A[0] へと移動させることになります。

for j in range(len(A)):
    if A[0] < A[j]:
        A[0], A[j] = A[j], A[0]

# ここの時点で max(A) == A[0]

for i in range(1, len(A)):
    for j in range(len(A)):
        if A[i] < A[j]:
            A[i], A[j] = A[j], A[i]

それでは二つ目のループの方を見ていきましょう。

i == 1

i == 1 のとき、内部のループはこのようになります。

for j in range(len(A)):
    if A[1] < A[j]:
         A[1], A[j] = A[j], A[1]

ここで A[0] に A の最大値が入っていたことを思い出すと、j == 0 のときに早速交換が起こることになります。よって A の最大値は A[1] に移動します。

そしてこれ以降交換は発生しません。なぜなら A の最大値が A[1] に収まった以上、もはやいかなる j も A[1] < A[j] を満たさないからです。

したがって、i == 1 における内部ループが終了した時点で A はこのようになっています。

i == 2

i == 2 のときはこのような内部ループになります。

for j in range(len(A)):
    if A[2] < A[j]:
        A[2], A[j] = A[j], A[2]

順を追ってみてみます。

j == 0

ここで A[i] < A[j]（すなわち A[2] < A[0] ）ならば交換が発生するので、A[0] < A[2] が事後条件として成立します。

j == 1

A の最大値は A[1] に収まっていましたから、A[i] < A[j]（すなわち A[2] < A[1]）は必ず成り立ちます。したがって、j == 0 の事後条件と合わせて A[0] < A[2] < A[1] がここでの事前条件として成り立ちます。ここでさらに A[2] と A[1] の交換が発生するので、A[0] < A[1] < A[2]、なおかつ A[2] は A の最大値、というのが事後条件として成立します。

j >= 2

先ほど A の最大値が A[2] に移動しましたから、i == 1 のときと同じ理屈でもう交換は発生しません。

よって i == 2 における内部ループの終了時点で A はこのようになっています。

もうこの時点でだいたい察しがついたと思いますが、i == X における内部ループが終了した時点で以下の 2 条件が成立します。

• A[0] から A[X] は昇順ソートされている
• A[X] は A の最大値

念のため帰納法できちんと確認しておきましょう。上の 2 条件が成り立っているものとして、i == X + 1 における内部ループを検証してみます。

i == X + 1 における内部ループでは A[X + 1] がソート済み領域に挿入されることになります。つまりやりたいことはこういうことです。

また A[0] から順に走査して交換できるところがあるか探すのですが、最初の方は交換は発生しません。A の左端は昇順にソート済みなわけですから、ここには A[X + 1] より小さい要素がかたまっているからです。

この「A[X + 1] 未満ゾーン」を抜けるととうとう交換が発生します。というか、今度は毎回交換が発生します。ここから A[X] まではさっきとは逆に A[X + 1] より大きい要素がかたまっているからです。

最終的に A[X] と A[X + 1] が交換され、A[X + 1] に A の最大値が収まります。そしてこれまで同様、ここからは最後まで交換は発生しません。よって帰納的に i == len(A) - 1 における内部ループが終了した時点で A が昇順ソートされていることがわかりました。

おわりに

コードを見れば一目瞭然ですが、このアルゴリズムは最良計算量・平均計算量・最悪計算量ともに $O(n^2)$ です。実用性よりも美しさを愛でましょう。ボゴソートよか実用的だけど