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

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

スターリンソートとは

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

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

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

Why do not you register as a user and use Qiita more conveniently?
  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
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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