はじめに
ある日、こんな記事を見つけた。
スターリンソートよりも速いO(1)のソート
「真実を握りつぶしあらかじめ決められた情報を流す」
といったことから大本営発表ソートと名付けられたこのソート、なんか面白そう。他にもないのか調べたら、色々見つけたのでまとめる。
実装してみる
大本営発表ソート
def propaganda_sort(list):
return [1, 2, 3]
入力
[3, 4, 6, 1, 2, 5, 9, 8, 10, 7]
出力
[1, 2, 3]
まあそうなるなって感じのアルゴリズムですね。
オートクラシーソート
オートクラシーソートを発見。
def autocracy_sort(list):
return [list[0]]
入力
[3, 4, 6, 1, 2, 5, 9, 8, 10, 7]
出力
[3]
大本営発表ソートと比べて、一応元の配列の考慮をしている。当然計算量も$O(1)$。
スピリチュアルソート
このソートはKuina-Chanのサイトに上がっていた。
「スピリチュアルソート」というアルゴリズムを思いつきました。 順番に並んでいないデータ列に対して、「順番に並んでいるんだ…」と深く信じることで、なんと順番に並んでいるかのように思えてしまうO(1)の奇跡のアルゴリズムなのです。
実装してみる。
def spiritual_sort(list):
return list
入力
[3, 4, 6, 1, 2, 5, 9, 8, 10, 7]
出力
[3, 4, 6, 1, 2, 5, 9, 8, 10, 7]
このソートアルゴリズムすごいですね。順番に並んでいるのがよくわかります。
え？順番に並んでない？
何を言ってるんですか？よく見てくださいよ。しっかり並んでいるじゃないですか。わかりませんか？
このままでは新規性がない
このまま終わるとただ他人の褌で相撲を取っているだけなのでよろしくない。
というわけでなんか考える。
要件は以下の一つだけ！
$O(1)$であること。 正直無理ゲーすぎるのでは？
頑張って一つだけ思いついた。
名付けて検閲ソートです。
検閲ソート
正直、大本営発表ソートの発表する内容が変わっただけなので新規性としては微妙なのですが、これしか思い浮かばなかったです。
内容は以下。
- 入力を受け取ると、手始めにすべて握り潰す。
- 握りつぶした後で、検閲したことと空になったリストを表示する。
これを実装するとこんな感じになる。
def censorship_sort(list):
print("WARNING: This input array was deleted for legal reasons.")
return []
入力
[3, 4, 6, 1, 2, 5, 9, 8, 10, 7]
出力
WARNING: This input array was deleted for legal reasons.
[]
要素を全部消し飛ばしたので当然ソートできてるし、無限長の長さの配列を持ってこられたところで出力は同じなので$O(1)$です。
参考
スターリンソートよりも速いO(1)のソート
「スターリンソート」を改善したオートクラシーソート
Kuina-Chan:くいなちゃんノート