おことわり
データ構造とアルゴリズム Advent Calendar 2022 10日目の記事です．
ネタ記事です．マジレスやめてください．
前置き
昨年，こんな論文が発表されました．
Is this the simplest (and most surprising) sorting algorithm ever?
この論文で紹介されているソートアルゴリズムはめちゃくちゃシンプルで，Pythonで実装すると次のようになります．
L = [3, 4, 1, 8, 2]
for i in range(len(L)):
for j in range(len(L)):
if L[i] < L[j]:
L[i], L[j] = L[j], L[i]
さて，このコードを実行した結果はどうなるでしょうか？？
実際に実行してみると・・・
print(L)
>>> [1, 2, 3, 4, 8]
となりました．感覚的には降順になりそうかなーと思うのですが，意外なことにも昇順になりました．
というのも，バブルソートをPythonで実装すると，
for i in range(len(L) - 1):
for j in range(i + 1, len(L)):
if L[i] < L[j]:
L[i], L[j] = L[j], L[i]
print(L)
>>> [8, 4, 3, 2, 1]
となるので，これがどうしても頭をよぎってしまうのでしょうか・・・？？（確かに似ている）
--- a.py
+++ b.py
@@ -1,5 +1,5 @@
-for i in range(len(L)):
- for j in range(len(L)):
+for i in range(len(L) - 1):
+ for j in range(i + 1, len(L)):
if L[i] < L[j]:
L[i], L[j] = L[j], L[i]
実は世の中には他にもおもしろソートがたくさんあるので，今回はそのいくつかを紹介したいと思います！！
以下Pythonとシェルスクリプトの知識を必要とするので，わからない人は適宜ググってください．
ボゴソート
概要
ボゴソートとは，乱択を使ったソートで平均計算量は驚異の $O(n\times n!)$ です！！ｽｺﾞｲ!! さらに最悪計算量は $O(\infty)$（停止しない） という恐ろしいアルゴリズムです．
アルゴリズム
さて，そのアルゴリズムは
1. リストをシャッフルして要素を無作為に並べる
2. ソートされているか確認する．確認されていたら終了
3. ソートされるまで1，2を繰り返す
という極めて単純なものです．ソートされるまでシャッフルし続けるという中々狂気じみたことをやっていますね．
実装
Pythonで実装してみます．実装自体はシンプルですね．
from random import randrange
def issorted(L: list[int]) -> bool:
"""リストがソートされているかどうかを判定する
"""
for i in range(len(L) - 1):
if L[i] > L[i + 1]:
return False
return True
def shuffle(L: list[int]) -> list[int]:
"""リストをシャッフルする
"""
for i in range(len(L)):
j = randrange(i, len(L))
L[i], L[j] = L[j], L[i]
return L
L = [3, 4, 1, 8, 2] # ランダムなリスト
while True:
if issorted(L):
break
L = shuffle(L)
print(*L)
所感
発想がおもろくて好き．技術者同士の会話で「あなたの好きなソートはなんですか？？」って聞かれたら「ボゴソート」って即答したいですね．
宇宙破壊コンピュータによるソート
概要
ボゴソートでのシャッフル操作を「世界線の分岐」と捉えることでソートを行います．シャッフルによってソートされなかった世界線は宇宙破壊コンピュータによって破壊されるので，残っている世界線では必ずソートされています．ｲﾐﾜｶﾗﾝ
きちんとした背景を知りたい方は とても強い計算量クラスのコンピュータとその実現方法 を読んでください．
アルゴリズム
1. リストをシャッフルして要素を無作為に並べる
2. ソートされているか確認する．ソートされていなかったら破壊する
3. もし破壊されていなければソート済みなので終了
実装
Pythonで実装してみます．ボゴソートの実装を流用することですぐに実装できます．
from random import randrange
def issorted(L: list[int]) -> bool:
"""リストがソートされているかどうかを判定する
"""
for i in range(len(L) - 1):
if L[i] > L[i + 1]:
return False
return True
def shuffle(L: list[int]) -> list[int]:
"""リストをシャッフルする
"""
for i in range(len(L)):
j = randrange(i, len(L))
L[i], L[j] = L[j], L[i]
return L
L = [3, 4, 1, 8, 2] # ランダムなリスト
L = shuffle(L)
if issorted(L):
print(*L)
else:
destroy() # 破壊！！
所感
ソートされていなかった世界線で「破壊」するのではなく，さらにシャッフルして世界線を増やすことで宇宙破壊コンピュータをスタックオーバーフローさせたいですね．
sleepソート
概要
配列の全ての要素に対して，一斉に「あなたの値が n なら n 秒後に出力してね！！よーいドン！！」を行うことでソートします．これで小さい値ほど早く出力されるので，小さい順にソートされます．実際はOSの制御云々の問題で正しくソートされる保証はないのでご注意を．
アルゴリズム
配列内の全ての要素に対して以下を同時に行う
1. 値をnとする．このとき，n秒後にnを出力する．
配列内の最大値を max_n とする．理論上は，max_n秒後に全ての要素が昇順に出力されている
実装
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]; do
f "$1" &
shift
done
wait
実際に実行してみると確かにソートされています・・・
% ./sleep.sh 5 3 4 2 4 6
2
3
4
4
5
6
所感
発想が天才のそれ．ソートに時間軸を持ち込むのは思いつかなかった．単純な疑問として，このソートの計算量はどうなるんだろう？？（このソートをバケットソートと解釈するか選択ソートと解釈するかで変わってきそう）
まとめ
ということで世の中の面白ソートをいくつか紹介してみました．どのソートもおもろいものばかりでしたね．せっかくなので自分でも何か考案してみたかったのですが，何も思いつきませんでした・・・ｺﾞﾒﾝﾅｻｲ．
「ぼくの考える最強のソートアルゴリズム」がある方はぜひコメントで教えてください！！
最後までお読みいただきありがとうございました！！