スターリンソートとは
ソートされていない要素を粛清することで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]
粛清感が薄れますが、このほうがすっきりしますね。
計算量も減りますし。
（ていうか粛清感ってなんだよ）