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

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

More than 1 year has passed since last update.

スターリンソートとは

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

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

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

Sirloin
社会人三年目。Atcoder茶。
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