はじめまして、サカイリです。プログラマとしてCS21で働いているPythonユーザです。
本日はちょっとしたネタということで、Twitterで話題になっていた「スターリンソート」をPythonで実装してみました。
（この記事は私がQiitaで投稿した同名記事『噂のスターリンソートをPythonで実装してみた』と同じ内容となっています。）
概要
ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる
— やんぎん (@4116You) July 28, 2019
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)で噂のスターリンソートを実装してみた
rubyでスターリンソートをやってみた（ブロック渡しも可能）
計算量O(n)の革命的なソートアルゴリズムをPHPでも
話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装した
スターリンソート in perl
すでにPythonで書いている人いるけど実装方法違うからいいよね！
実装
リスト内包表記で1行実装できます。
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]
やっていることは簡単で、与えられた数字配列のデータを順番に確認していき、ひとつ前の数字と比較をしてそれ以上の数であればlistにappendします。
しかしリスト内包表記では変数への代入が許可されていないため、前の数字を保持することができません。そこでlistのappend（tmp.append(i)）と参照（tmp[-1]）を利用することで実現しています。
リスト内包表記について「python3と秘密のリスト内包表記」が非常に参考になりました。
