最もシンプルで(驚くべき)ソートアルゴリズム？

こういうツイートを見かけたので元の論文を読んだり実装してみたりしました

世界一単純な? ソートアルゴリズム。
for i=1..n:
for j=1..n:
if a[i]<a[j]:
swap(a[i], a[j])
一見バブルソートのように見えるが、if判定の不等号の向きがバブルソートとは逆になっているのに、それでもソートされる。https://t.co/1qSnomUrUR

— 新山祐介 (Yusuke Shinyama) (@mootastic) 2021å¹´10月6æ—¥

注意点ですが、このアルゴリズム自体はよく使われるソートアルゴリズムと比べて特に利点があるわけではなくてネタ的な話です。

元論文
arxiv.org

実装(Python)

この記事のソートでは昇順に並べます

ICan’tBelieveItCanSort

というわけで論文で言うところのICan’tBelieveItCanSortを実装してみました。

Algorithm 1 ICan’tBelieveItCanSort (論文より)

https://arxiv.org/abs/2110.01111

二重ループして\(j\)番目の要素が\(i\)番目の要素よりも大きかったら交換するだけなので単純です。
冒頭のツイートでも書かれていたように、以下で実装している他のソートとひと目見比べてみると交換するときの大小の条件が逆になっているように見えなくもないです。

def i_cant_believe_it_can_sort(A: list):
  n = len(A)
  for i in range(n):
    for j in range(n):
      if A[i] < A[j]:
        A[i], A[j] = A[j], A[i]
  return A

ExchangeSort

論文中にはExchangeSortというのも出てきたのでそれも実装してみました。
ちなみに元の論文では、ExchangeSortの内側の\(i\)からのループを先頭からのループと間違えて実装したときにICan’tBelieveItCanSort)を発見したというふうに書かれていました(その場合は大小の条件が逆なので降順になる)

def exchange_sort(A: list):
  n = len(A)
  for i in range(n):
    for j in range(i + 1, n):
      if A[i] > A[j]:
        A[i], A[j] = A[j], A[i]
  return A

バブルソート

参考用に同様にバブルソートを実装してみました。
隣同士の要素を比べて順番が降順になっていたら入れ替えます。
実装的にはICan’tBelieveItCanSortとどっちがシンプルかというのはなんとも言い難いです

def bubble_sort(A: list):
  n = len(A)
  for i in range(n - 1):
    for j in range(n - 1):
      if A[j] > A[j + 1]:
        A[j], A[j + 1] = A[j + 1], A[j]
  return A

なんでソートできるの？

ICan’tBelieveItCanSortがどう動くか適当な配列を例に説明してみましょう。

最初は[2, 5, 9, 7, 1, 7]とします。

\(j\)番目の要素が\(i\)番目の要素よりも大きかったら交換するので、最初の\(i=0\)のループ後は配列の先頭に最大の要素が入ります。
i=0, j=0, [2, 5, 9, 7, 1, 7]
i=0, j=1, [5, 2, 9, 7, 1, 7]
i=0, j=2, [9, 2, 5, 7, 1, 7]
i=0, j=3, [9, 2, 5, 7, 1, 7]
i=0, j=4, [9, 2, 5, 7, 1, 7]
i=0, j=5, [9, 2, 5, 7, 1, 7]
上の例を見てもわかるように\(i\)番目に最大の要素が来るとそれ以上交換は行われなくなります

\(i=1\)のループでは、最初が[9, 2, 5, 7, 1, 7]で
i=1, j=0, [2, 9, 5, 7, 1, 7]
i=1, j=1, [2, 9, 5, 7, 1, 7]
以下略

\(i=0\)のループで先頭に最大の要素があるのでこれ以降\(j\)に関するループは\(j=i-1\)までやれば十分になっています(それ以上やっても交換は行われない)
このことから\( j < i \)となっています。なので最初に大小の比較の条件が逆に見える、という話がありましたが、i番目の方に大きい要素が来るのは配列の後ろの方に大きい要素が来るのと同じなので大小の条件は逆ではなさそうというのがわかります

\(i=2\)のループでは、最初が[2, 9, 5, 7, 1, 7]で
i=2, j=0, [2, 9, 5, 7, 1, 7]
i=2, j=1, [2, 5, 9, 7, 1, 7]
以下略

\(i=3\)のループでは、最初が[2, 5, 9, 7, 1, 7]で
i=3, j=0, [2, 5, 9, 7, 1, 7]
i=3, j=1, [2, 5, 9, 7, 1, 7]
i=3, j=2, [2, 5, 7, 9, 1, 7]
以下略

\(i=4\)のループでは、最初が[2, 5, 7, 9, 1, 7]で
i=4, j=0, [1, 5, 7, 9, 2, 7]
i=4, j=1, [1, 2, 7, 9, 5, 7]
i=4, j=2, [1, 2, 5, 9, 7, 7]
i=4, j=3, [1, 2, 5, 7, 9, 7]
以下略

残りは同じ感じなので省略します。

上で試してみた結果のように、このアルゴリズムでは\(i\)のループが終わった時点では先頭から\(i\)番目までの要素について、次の要素の方が大きいもしくは等しい状態、つまり昇順の状態になります。
なので最後まで\(i\)のループを行うとすべての要素が昇順になることが言えます(論文には証明があります)

挙動を大雑把に理解するために\(i\)に関するそれぞれのループ後の配列をみると、\(i=1\)以降のループでは実質的には挿入ソートと同じ挙動になっていることがわかります。

i=0, [9, 2, 5, 7, 1, 7]
i=1, [2, 9, 5, 7, 1, 7]
i=2, [2, 5, 9, 7, 1, 7]
i=3, [2, 5, 7, 9, 1, 7]
i=4, [1, 2, 5, 7, 9, 7]
i=4, [1, 2, 5, 7, 7, 9]

挿入ソートでは\(i\)番目の要素をそれ以前の要素と見比べて適切な位置に挿入してそれ以降の要素を一つ後ろにずらします。
このアルゴリズムでは\(i\)番目の要素との交換を使って、挿入ソートでいうところの挿入して要素を一つずつ後ろにずらす操作を実現していることになります。
挿入ソート - Wikipedia

なのでコードからは想像しづらいですが\(i=0\)のループで最大値を先頭に持ってきて\(i=1\)以降のループでは挿入ソートのようなことをしているという挙動としては結構わかりやすいことをしていることがわかりました

コードを再掲

def i_cant_believe_it_can_sort(A: list):
  n = len(A)
  for i in range(n):
    for j in range(n):
      if A[i] < A[j]:
        A[i], A[j] = A[j], A[i]
  return A

おまけ

論文中にはIt is difficult to imagine that this algorithm was not discovered before,
but we are unable to find any references to it.と書かれていますが、検索などを使って調べた人によると今回のソートアルゴリズムと同じものの実装例や質問が結構見つかるらしいです
Some links to discussions and/or accidental discoveries of this algorithm: OP (2... | Hacker News