172
68

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2019-07-30

スターリンソートとは

今話題の計算量が $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]

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

(ていうか粛清感ってなんだよ)

172
68
9

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
172
68

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?