スターリンソートをまともに使えるようにしてみた(オーダわかんね)

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる

— やんぎん (@4116You) July 28, 2019

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell - Qiita

が面白そうだったのでまともなソートに使えないか考えてみました

考え方

1. 粛清する
2. 粛清された人を生き返らせてまた粛清する
3. 1の生き残りと2の生き残りをマージする
4. 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