概要

ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる
— やんぎん (@4116You) July 28, 2019

Pythonワンライナーでこれを実現する。
ただし、コードゴルフや過度な難読化を目的とはしない。

なお、入力はコマンドライン引数として与えられることとする。

最初の実装

Haskell版を移植したもの。ワンライナーらしい素直な実装である。Wandbox

print(*(lambda func: (lambda arr: func(func, arr)))(lambda func, arr: [] if not arr else arr if len(arr) == 1 else [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else func(func, [arr[0], *arr[2:]]))([*map(int, __import__('sys').argv[1:])]))

これを読み易く整形、適宜コメントを加えると次のようになる。

print(*
    # 再帰可能にする為に高階関数を噛ませる
    (lambda func:
        (lambda arr:
            func(func, arr)
        )
    )
    # ソート実装本体
    (lambda func, arr:
        # arrが空リストなら、空リストを返す
        []                             if not arr          else
        # arrが長さ1であるなら、そのままarrを返す
        arr                            if len(arr) == 1    else
        # 粛清が必要無い場合、最初の要素を通過させる
        [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else
        # 粛清が必要な場合、粛々と粛清する
        func(func, [arr[0], *arr[2:]])
    )
    # コマンドライン引数を数値列に変換
    ([*map(int, __import__('sys').argv[1:])])
)

ワンライナービギナー向けに書き下すと、こんな感じ。

def higher_func(func):
    def inner(arr):
        return func(func, arr)

    return inner


def stalin_sort(func, arr):
    if not arr:
        return []

    if len(arr) == 1:
        return arr

    if arr[0] <= arr[1]:
        return [arr[0], *func(func, arr[1:])]

    return func(func, [arr[0], *arr[2:]])

stalin_sort = higher_func(stalin_sort)     # 本来はデコレータを使うべき


import sys

arr = [*map(int, sys.argv[1:])]
print(*stalin_sort(arr))

想定される抵抗と、その鎮圧

抵抗を予期して対処する為には、検閲が必要である。
次のように検閲関数を適当に用意し、引数censorとして渡す。

# 再帰可能にする為、また事前検閲の為に高階関数を噛ませる
(lambda func, censor:
    (lambda arr:
        func(func, censor(arr))
    )
)
(
    # 第一引数： ソート実装本体
    (lambda func, arr: 
        略
    ),
    # 第二引数： 検閲関数
    (lambda arr: 
        検閲し、必要なら新たなリストを返す
    )
)
# ソート元リスト
(略)

以降、検閲関数の実装を考える。

対人海戦術

ソート対象のリストが過度に長大で有る場合、MemoryErrorやRecursionErrorを引き起こす恐れがある。¹
これはスターリンの意向に沿わないので、適当な方法で排除しなければならない。

ここでは、要素数が1024を超える入力²を与える輩には相応の措置を与えるようにする。

要素の切り詰め

恐らく最も穏便且つ寛大な方法である。

# 第二引数： 検閲関数
(lambda arr: arr[:1024])

大粛清

単純な方法であるが、インパクトに欠ける。

# 第二引数： 検閲関数
(lambda arr: [] if 1024 < len(arr) else arr)

例外送出

raise文は使えないので、generator.throwを利用する。
また例外は決して凡庸なものであってはならない。type関数でBaseExceptionを継承し、特別に生成する。³

# 第二引数： 検閲関数
(lambda arr: 
    (_ for _ in []).throw(
        type('StalinPurge', (BaseException,), {}), 'array is too long'
    ) if 1024 < len(arr) else arr
)

強制遮断

例外はキャッチされてしまう恐れがある。
それを避ける為には、プロセス自体を落としてやるのが有用である。⁴

# 第二引数： 検閲関数
(lambda arr: 
    (print("You're purged."), __import__('sys').exit(1)) if 1024 < len(arr) else arr
)

対不正入力

数字列の入力を望んでいるが、不敬の輩は不純物を交え妨害してくるだろう。
これに備えて、入力部分及び検閲関数を次のように修正する。

# 再帰可能にする為、また事前検閲の為に高階関数を噛ませる
(lambda func, censor:
    (lambda arr:
        func(func, censor(arr))
    )
)
(
    # 第一引数： ソート実装本体
    (lambda func, arr: 
        略
    ),
    # 第二引数： 検閲関数
    (lambda raw_arr:
        # 数値列化してからの検閲
        (lambda arr:
            略
        )
        # 関数呼び出しは左結合なので、括弧で優先してやる必要がある
        (
            # 生入力に対する検閲
            (lambda raw_arr: 
                検閲の結果を踏まえ、リストを数値列化して返す
            )
            (raw_arr)
        )
    )
)
# 
(__import__('sys').argv[1:])

不純物の排除

不純要素だけを排斥する、やはり寛大な方法である。⁵

# 生入力に対する検閲
(lambda raw_arr: 
    [int(e) for e in raw_arr if e.isdecimal()]
)

連帯責任

先の大粛清・例外送出・強制遮断のいずれかを用いてソート自体を拒絶する。
その場合次のように条件を指定してやれば良い。

# 生入力に対する検閲
(lambda raw_arr: 
    粛清処理 if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)]
)

成果物

せっかくなので、一番書くのが面倒だった例外処理を採用する。

print(*
    # 再帰可能にする為に高階関数を噛ませる
    (lambda func, censor:
        (lambda arr:
            func(func, censor(arr))
        )
    )
    (
        # 第一引数： ソート実装本体
        (lambda func, arr:
            # arrが空リストなら、空リストを返す
            []                             if not arr          else
            # arrが長さ1であるなら、そのままarrを返す
            arr                            if len(arr) == 1    else
            # 粛清が必要無い場合、最初の要素を通過させる
            [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else
            # 粛清が必要な場合、粛々と粛清する
            func(func, [arr[0], *arr[2:]])
        ),
        # 第二引数： 検閲関数
        (lambda raw_arr:
            (lambda arr:
                (_ for _ in []).throw(
                    type('StalinPurge', (BaseException,), {}), 'array is too long'
                ) if len(arr) > 1024 else arr
            )
            (
                (lambda raw_arr: 
                    (_ for _ in []).throw(
                        type('StalinPurge', (BaseException,), {}), 'spy is found.'
                    ) if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)]
                )
                (raw_arr)
            )
        )
    )
    # コマンドライン引数を変換せずに渡す
    (__import__('sys').argv[1:])
)

一行に詰めるとこんな感じ。600文字以内で書けた。Wandbox

print(*(lambda func, censor: (lambda arr: func(func, censor(arr))))((lambda func, arr: [] if not arr else arr if len(arr) == 1 else [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else func(func, [arr[0], *arr[2:]])), (lambda raw_arr: (lambda arr: (_ for _ in []).throw(type('StalinPurge', (BaseException,), {}), 'array is too long') if len(arr) > 1024 else arr)((lambda raw_arr: (_ for _ in []).throw(type('StalinPurge', (BaseException,), {}), 'spy is found.') if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)])(raw_arr))))(__import__('sys').argv[1:]))

お手元のPythonでも、 python -c "上記コード" 数値1 数値2 数値n で試せる。

標準入力を使いたいなら、
__import__('sys').argv[1:]を__import__('sys').stdin.read().split()に差し替えれば良い。

追記

本家にプルリクを出してみた。
変更した仕様は次のとおり：

関数stalin_sortを用意し、コマンドライン引数の読み取りを廃した。
数値列以外の引数を拒むようにした。

~~今後進展があったらさらに追記する。通ると良いなぁ。~~
通った。まじか。とても嬉しい。

先駆者たち

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

Python

黒魔術

闇の力を駆使すればO(1)でスターリンソートなぞ容易いものよ

参考

特に何も考えずに100万長のリストを与えてみたら、PCが粛清された。 ↩
歴史に疎いので、スターリンらしい上限値が思い付かない。詳しい人、教えて下さい。 ↩
本来ならBaseExceptionは継承してはならない。スターリン特例である。 ↩
SystemExitが捕捉できるとか、そういうことは言っちゃいけない。 ↩
str.isdecimalは想像するより多くの『数字』を看過する。アラビア数字以外認めないのであれば all(c in set('0123456789') for c in e) あたりが適当か。 ↩

Pythonワンライナーでスターリンソート

概要