1. はじめに

Qiita初投稿です。よろしくお願いします。

先日からプログラミングを勉強しているのですが、ソートについて勉強していたらこんな面白い記事を見つけました。

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた

元ネタはこのツイートらしいです。

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる
— ん (@4116You) July 28, 2019

関連事項を検索すると新しいソートが出てくる出てくる。せっかくなのでPythonとQiitaの使い方の練習も兼ねて、いろいろ実装してみました。

2. 注意

初心者のコーディングなのでお見苦しい点があればご指摘いただきたいです。
Pythonの埋め込みソートが$O(N\log N)$なので、今回はそれより計算量の少ないソートのみを紹介します(なのでボゴソートとかはやりません)。

3. ソートの紹介

3.1. スターリンソート

みんなだいすきスターリンソート。Pythonで実装されてる方もいらっしゃいますね。

話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装した

与えられた配列について、昇順になっていない要素を†粛清†することによって、配列を昇順にソートします。昇順になっていさえすればそれはもうソートですよね。
初心者なりの実装方法はこんなかんじ。

sta_sort.py

#Stalin_sort
def sta_sort(L):
    R = []
    maxi = 0
    for i in range(len(L)):
        if i == 0:
            R.append(L[i])
            maxi = L[i]
        else:
            if L[i] >= maxi:
                R.append(L[i])
                maxi = L[i]
            else:
                pass
    return(R)

入力
[3, 8, 11, 5, 29, 7, 18, 80]
出力
[3, 8, 11, 29, 80]

うん、いい感じ。
粛清してる感じがそんなにないのですがそこはご愛敬。

ちなみにPythonの場合、文字列の配列も辞書式順序に従ってソートしてくれます。

入力
["c","o","m","p","u","t","e","r"]
出力
['c', 'o', 'p', 'u']

これの計算量は$O(N)$です。

3.2. アベソート

別名を「洗脳ソート」とも。こちらの記事が詳しいです。

Ruby と Rust でアベソートを実装してみた
 ［ネタ］要素数が変化しないO(n)のソートアルゴリズム

スターリンソートでは、粛清が起こるゆえに入力と出力の配列の長さが一般には同じにならないことが問題でした~~(ほかにもあるが)~~。では、昇順に従わない要素を改ざん(あるいは洗脳)すれば、要素数を同じにすることができるのでは？

abe_sort.py

#Abe_sort
def abe_sort(L):
    maxi = 0
    for i in range(len(L)):
        if i == 0:
            maxi = L[i]
        else:
            if L[i] >= maxi:
                maxi = L[i]
            else:
                L[i] = maxi
    return(L)

整数/文字列の両方で試してみます。

入力
[3, 8, 11, 5, 29, 7, 18, 80]
出力
[3, 8, 11, 11, 29, 29, 29, 80]

入力
["c","o","m","p","u","t","e","r"]
出力
['c', 'o', 'o', 'p', 'u', 'u', 'u', 'u']

頼むから炎上しないでくれ。
計算量は同じく$O(N)$ですね。

3.3. コミューンソート

要素を足してみんなで分け合おうという共産主義的ソートです。文字列には残念ながら使えなさそうですが、こちらも配列の長さが変化しないのでスターリンソートより一歩優れていますね(は？)
こちらの記事を参考にさせていただいています。
ソートに対する理想と現実(スターリンやAbeから)

3.3.1. ideal

理想の共産主義を描いたソートです。

com_sort_ideal.py

#Commune_sort_ideal
def com_sort_ideal(L):
    S = 0
    for i in range(len(L)):
        S = S + L[i]
    Dist = S // len(L)
    R = [Dist for _ in range(len(L))]
    return(R)

出力の要素が浮動小数点数になると見た目が汚いので余った端数はぼくがもらうことにしました。文句ある？
実際にリストを食わせてみましょう。

入力
[3, 8, 11, 5, 29, 7, 18, 80]
出力
[20, 20, 20, 20, 20, 20, 20, 20]

マルクスもびっくりの結果になりました。計算量は$O(N)$。

3.3.2. real

現実の厳しさを描いたソートです。

com_sort_real.py

#Commune_sort_real
def com_sort_real(L):
    S = 0
    for i in range(len(L)):
        S = S + L[i]
    R = [0 for _ in range(len(L)-1)]
    R.append(S)
    return(R)

入力
[3, 8, 11, 5, 29, 7, 18, 80]
出力
[0, 0, 0, 0, 0, 0, 0, 161]

キムソートと言って差し支えないでしょう。
計算量は$O(N)$。

3.4. プロパガンダソート

別名「大本営発表ソート」とも。
こちらの記事を参考にさせていただきました。
スターリンソートよりも速いO(1)のソート

元記事様より引用。

我々が目指すべきは$O(1)$のアルゴリズムです。

どこまでも計算量に貪欲であるこの態度に、私は非常に感動しました。
アルゴリズムも非常に簡単。

いかなる入力に対しても、あらかじめ用意したソート済み配列（リスト）を返す。

これなら私にも実装できそうです。

pro_sort.py

#Propaganda_sort
def pro_sort(L):
    R = [1,2,3]
    return(R)

整数/文字列の両方を入力として食わせてみます。

入力
[3, 8, 11, 5, 29, 7, 18, 80]
出力
[1, 2, 3]

入力
["c","o","m","p","u","t","e","r"]
出力
[1, 2, 3]

「真実を握りつぶしあらかじめ決められた情報を流す」という意味で、「大本営発表」という名前がついています。
これで計算量を$O(1)$にまで抑えることができました。

3.5. オートクラシーソート

いくら計算量を抑えるためとはいえ、入力を完全に無視するのはけしからん。
ということでこちらのオートクラシーソートを実装していきます。

「スターリンソート」を改善したオートクラシーソート

リストの一番初めの値(すなわち「独裁者」)以外を全て消してしまえば、独裁政権を維持することができます。

auto_sort.py

#Autocracy_sort
def auto_sort(L):
    R = [L[0]]
    print(R)

こちらも整数/文字列の両方に対応しています。

入力
[3, 8, 11, 5, 29, 7, 18, 80]
出力
[3]

入力
["c","o","m","p","u","t","e","r"]
出力
['c']

入力に応じて出力が変わった！やったね！
計算量も$O(1)$なので、これが文句なしの最強ソートですね。独裁最高！

また、pythonではその恩恵を受けることはかないませんでしたが、3.4.で紹介したプロパガンダソートとこちらのオートクラシーソートは、入力が無限の長さを持つ配列でも有限時間で計算が可能です。

4. 新規性がない

この記事を書いてみて思ったのですが、人様の記事のアルゴリズム紹介しかしてないので新規性がありません。

思ったんですけど、今までのアルゴリズムって元の配列ちゃんとキープしてなくないですか？
ということで

計算量$O(N)$以下で
配列の要素が昇順に並んでいて
配列長を変えず
さらに元の配列の値が(何らかの形で)保存される

アルゴリズムを考えてみました。

5. 積み立てソート

英語だとstacking sortといったところでしょうか。いい名前が思いつかなかったのでコメントで募集しています。
アルゴリズムは単純で、出力する配列の第$n$番目に、元の配列の第$1$番目から第$n$番目までの総和を入れます。

Pythonによるコードはこんな感じ。

stack_sort.py

#Stacking_sort
def stack_sort(L):
    R = []
    library = 0
    for i in range(len(L)):
        library = library + L[i]
        R.append(library)
    return(R)

本当にソートできているのか確かめてみましょう。

入力
[3, 8, 11, 5, 29, 7, 18, 80]
出力
[3, 11, 22, 27, 56, 63, 81, 161]

昇順に並んでいるので文句ないですよね。

積み立てソートのメリット

元の配列が復元できる

実際に次の関数によって、ソート前の配列を復元することが可能です。

stack_rest.py

#Stacking_restoration
def stack_rest(L):
    R = []
    x = 0
    for i in range(len(L)):
        if i == 0:
            R.append(L[i])
        else:
            x = L[i] - L[i-1]
            R.append(x)
    return(R)

先ほどの出力をstack_rest()に入れてみます。

入力
[3, 11, 22, 27, 56, 63, 81, 161]
出力
[3, 8, 11, 5, 29, 7, 18, 80]

リストが復元されました。

入力と出力の配列長が等しい

それはそう。

計算量が$O(N)$

ついでに復元の際の計算量も$O(N)$。

積み立てソートのデメリット

使用範囲が限られる

文字列はもちろんのこと、整数に話を限れば自然数しか扱うことができません($0$は自然数)。浮動小数点数においても、$0$以上の数しか扱えないため、このソートの適用範囲はぐっと狭まります。
実は負の数の場合にも一応実装はできます。

stacking_sort_alt.py

#Stacking_sort_alternative
def stack_sort_alt(L):
    R = []
    library = 0
    for i in range(len(L)):
        library = library + abs(L[i])
        R.append(library)
    return(R)

しかしながら、これは積み上げソート最大の強みである「もとの配列が復元できる」特性を完全に失っているため、いい解決策とは思えません。

無限長の配列には対応できない

仕方ない。

6. 比較

各種ソートの比較です。

ソートの種類	計算量	配列長	配列の要素	無限長配列の入力
sta_sort	$O(N)$	保存しない	部分的に保存する	対応できない
abe_sort	$O(N)$	保存する	部分的に保存する	対応できない
com_sort_ideal	$O(N)$	保存する	保存しない	対応できない
com_sort_real	$O(N)$	保存する	保存しない	対応できない
pro_sort	$O(1)$	保存しない	保存しない	対応できる
auto_sort	$O(1)$	保存しない	1つだけ保存する	対応できる
stack_sort	$O(N)$	保存する	保存する(復元可能)	対応できない

7. 感想

非常に上質なクソができました。Markdown記法にしっかり慣れたので今回は及第点だと思います。
stack_sortについては和名/英語名募集中なのでコメントにお願いします。
またコードの改善点、俺はこんなソート考えたぞなどなど、コメントでいただけると喜びます。ただし計算量は$O(N)$以下に限る。

引用させていただいた各記事のauthorのみなさまに感謝します。

8. おわりに

def python_sort(L):
    L.sort()
    return(L)

入力
[3, 8, 11, 5, 29, 7, 18, 80]
出力
[3, 5, 7, 8, 11, 18, 29, 80]

組み込み関数しか勝たん。

Pythonで学ぶネタソートまとめ