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

噂のスターリンソートをPythonで実装してみた

概要


Twitterで話題になっていたスターリンソートをPythonで実装してみました。

スターリンソートとは

I came up with asingle pass O(n) sort algorithm I call StalinSort.
You iterate down the list of elements checking if they're in order.
Any element which is out of order is eliminated.
At the end you have asorted list.

公式より引用
与えられたリストからソートされていない要素を除いた昇順リストを生成することでソートします。
また、同じ数字がある場合は残しています。
(例)6, 2, 5, 7, 3, 8, 8, 4 -> 6, 7, 8, 8

先駆者たち

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell
計算量O(n)で噂のスターリンソートを実装してみた
[Rust] スターリンソートと PartialOrd
rubyでスターリンソートをやってみた(ブロック渡しも可能)
計算量O(n)の革命的なソートアルゴリズムをPHPでも
話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装した
スターリンソート in perl

すでにPythonで書いている人いるけど実装方法違うからいいよね!

実装

リスト内包表記で1行でした。
リスト内包表記については「python3と秘密のリスト内包表記」が非常に参考になりました。

stalinsort.py
def stalinsort(targets):
    return [(tmp.append(i), i)[1] for tmp in [[targets[0]]] for i in targets if i >= tmp[-1]]

original_list = [6, 2, 5, 7, 3, 8, 8, 4]
sorted_list = stalinsort(original_list)
print('original', original_list)
print('sorted', sorted_list)

実行結果

original [6, 2, 5, 7, 3, 8, 8, 4]
sorted [6, 7, 8, 8]

実装できました。

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
Comments
No 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
ユーザーは見つかりませんでした