スターリンソートとは

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる

— やんぎん (@4116You) July 28, 2019

今話題の計算量が $O(n)$ で済む驚異のソートアルゴリズム、スターリンソートをご存知でしょうか。

中身はいたってシンプルで、ソートされていない要素を削除（粛清）して、強引に昇順リストを生成します。
例えば、[1, 2, 1, 1, 4, 3, 9]というリストをスターリンソートすると[1, 2, 4, 9]になります。（1, 1, 3が粛清されました）

粛清というパワーワードがポイントですね。

既に先人達が色々な言語で実装しておりますが、知らない言語しかなかったのでこの度Pythonで実装してみました。

先駆者達

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell
計算量O(n)で噂のスターリンソートを実装してみた
[Rust] スターリンソートと PartialOrd
rubyでスターリンソートをやってみた（ブロック渡しも可能）

Pythonで実装

コード

data = [1, 2, 1, 1, 4, 3, 9]
purge = [] #purge : [動詞]〜を粛清する

# 粛清すべき要素のインデックスを探す
tmp = data[0] - 1
for i, e in enumerate(data):
    if e < tmp:
        purge.append(i)
    else:
        tmp = e

# Let's 粛清!!
for i, e in enumerate(purge):
    data.pop(e - i)

print(data)

標準出力

[1, 2, 4, 9]

1 1 3が粛清され、見事に昇順ソートされましたね。
ルールに従わない要素は消す、なんとも強引なアルゴリズムです。

よいこのみなさんは他の正しいソートアルゴリズムを使いましょう。

追記

pop()は粛清感が出るけど計算量が $O(n)$ じゃなくなる、とのコメント多数頂いたのでpop()を使わない実装を考えました。

data = [1, 2, 1, 1, 4, 3, 9]
purged_data = [] #purge : [動詞]〜を粛清する
tmp = data[0] - 1

for i, e in enumerate(data):
    if tmp <= e:
        purged_data.append(e)
        tmp = e
print(purged_data)

[1, 2, 4, 9]

粛清感が薄れますが、このほうがすっきりしますね。
計算量も減りますし。

（ていうか粛清感ってなんだよ）