Help us understand the problem. What is going on with this article?

【ネタ】O(1)のソートアルゴリズム

はじめに

ある日、こんな記事を見つけた。
スターリンソートよりも速いO(1)のソート

「真実を握りつぶしあらかじめ決められた情報を流す」

といったことから大本営発表ソートと名付けられたこのソート、なんか面白そう。他にもないのか調べたら、色々見つけたのでまとめる。

実装してみる

大本営発表ソート

Propaganda.py
def propaganda_sort(list):
    return [1, 2, 3]

入力
[3, 4, 6, 1, 2, 5, 9, 8, 10, 7]
出力
[1, 2, 3]
まあそうなるなって感じのアルゴリズムですね。

オートクラシーソート

オートクラシーソートを発見。

Autocracy.py
def autocracy_sort(list):
    return [list[0]]

入力
[3, 4, 6, 1, 2, 5, 9, 8, 10, 7]
出力
[3]

大本営発表ソートと比べて、一応元の配列の考慮をしている。当然計算量も$O(1)$。

スピリチュアルソート

このソートはKuina-Chanのサイトに上がっていた。

「スピリチュアルソート」というアルゴリズムを思いつきました。 順番に並んでいないデータ列に対して、「順番に並んでいるんだ…」と深く信じることで、なんと順番に並んでいるかのように思えてしまうO(1)の奇跡のアルゴリズムなのです。
実装してみる。

Spiritual.py
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)$であること。 正直無理ゲーすぎるのでは?
頑張って一つだけ思いついた。

名付けて検閲ソートです。

検閲ソート

正直、大本営発表ソートの発表する内容が変わっただけなので新規性としては微妙なのですが、これしか思い浮かばなかったです。
内容は以下。
1. 入力を受け取ると、手始めにすべて握り潰す。
2. 握りつぶした後で、検閲したことと空になったリストを表示する。

これを実装するとこんな感じになる。

Censorship.py
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:くいなちゃんノート

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away