ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる
— やんぎん (@4116You) July 28, 2019
計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell - Qiita
が面白そうだったのでまともなソートに使えないか考えてみました
考え方
- 粛清する
- 粛清された人を生き返らせてまた粛清する
- 1の生き残りと2の生き残りをマージする
- 2,3を粛清された人が0になるまで繰り返す
オーダー
うーんわからない(笑)...
マージ部分で$O(N^2)$はかかってる気がするので$O(N^2logN)$とかいう恐ろしい予想が立ちます
誰か考えて()
Pythonで実装
from functools import reduce
def teppop(comp_method=int.__le__):
def _teppop(acc, elm):
# acc = (sorted, purged)
if len(acc[0]) == 0 or comp_method(acc[0][-1], elm):
acc[0].append(elm)
else: # 粛清
acc[1].append(elm)
return acc
return _teppop
def marge_lis(a, b, comp_method=int.__le__):
res = []
a_len, b_len = len(a), len(b)
while a_len > 0 and b_len > 0:
if comp_method(a[0], b[0]):
res.append(a.pop(0))
a_len -= 1
else:
res.append(b.pop(0))
b_len -= 1
res += b if a_len == 0 else a
return res
def pure_stalin_sort(lis, reversed=False):
cm = type(lis[0]).__ge__ if reversed else type(lis[0]).__le__
return reduce(teppop(comp_method=cm), lis, [[], []])[0]
def stalin_sort(lis, reversed=False):
cm = type(lis[0]).__ge__ if reversed else type(lis[0]).__le__
res, purged = reduce(teppop(comp_method=cm), lis, [[], []])
while len(purged) > 0:
tmp, purged = reduce(teppop(comp_method=cm), purged, [[], []])
res = marge_lis(res, tmp, comp_method=cm)
return res
if __name__=="__main__":
test_lis = [1, 2, 1, 1, 4, 3, 9]
print(test_lis, "=>", stalin_sort(test_lis))
from random import randint
for _ in range(5):
test_lis = [randint(1,20) for _ in range(randint(10, 20))]
res = stalin_sort(test_lis)
assert sorted(test_lis) == res
print(test_lis, "=>", res)
実行結果例
[1, 2, 1, 1, 4, 3, 9] => [1, 1, 1, 2, 3, 4, 9]
[6, 9, 12, 13, 10, 17, 3, 20, 15, 5, 18, 2] => [2, 3, 5, 6, 9, 10, 12, 13, 15, 17, 18, 20]
[4, 6, 18, 16, 2, 10, 16, 10, 2, 17, 11, 9, 4, 15, 4, 19, 7] => [2, 2, 4, 4, 4, 6, 7, 9, 10, 10, 11, 15, 16, 16, 17, 18, 19]
[9, 19, 15, 12, 4, 17, 1, 3, 12, 18, 15, 12, 17, 10, 6] => [1, 3, 4, 6, 9, 10, 12, 12, 12, 15, 15, 17, 17, 18, 19]
[8, 19, 3, 9, 17, 20, 3, 16, 18, 10, 19] => [3, 3, 8, 9, 10, 16, 17, 18, 19, 19, 20] 4, 15, 20]
[8, 3, 6, 14, 12, 14, 12, 15, 20, 4, 5, 13, 3, 7, 1, 12, 1, 8, 2] => [1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 12, 12, 12, 13, 14, 14, 15, 20]
粛清とreduceをかけてみました(何も面白くない)
余談
オリジナルスターリンソート、Rubyだと簡潔に書けます。
def stalin_sort(lis)
$top = lis[0]
lis.select {|elm|
if $top <= elm then $top = elm end
}
end
p stalin_sort([1, 2, 1, 1, 4, 3, 9]) # => [1, 2, 4, 9]
闇を使うとPythonでも比較的短くなる...?
def stalin_sort(lis):
b = {"top": lis[0]}
return list(filter(lambda elm: not(b["top"] > elm or b.__setitem__("top",elm)), lis))
print(stalin_sort([1, 2, 1, 1, 4, 3, 9])) #=> [1, 2, 4, 9]
最後に
ゴミ記事を量産しまして誠に申し訳ございませんでした。m(_ _)m