やさしいスターリンソート入門【実用的】

概要

最近、巷ではスターリンソートというソートが流行っています。

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

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

スターリンといえば粛清、というような考え方によるソートです。
しかし、ちょっと待ってください。スターリンには粛清以外の選択肢もありました。
すなわち、シベリア送りです。

この記事では、粛清ではなくシベリア送りによる「やさしいスターリンソート」を実装し、データの量を減らすことなく、計算量を減らします。
それによって、銀河に平和をもたらします。
※このソートは、「スターリンソート」とは異なるのでご注意ください。

「やさしいスターリンソート」とは

スターリンソートでは、ソート順に反する要素を粛清することによりソートをしていました。
やさしいスターリンソートでは、粛清などという怖いことはしません。
代わりに、すべての要素をシベリアに送ります。大きいとか小さいとか関係ありません。皆平等にシベリア送りです。
ただし、シベリアに送る時に、データの値が1であればシベリアの1番地、データの値が2であればシベリアの2番地、…データの値がNであればシベリアのN番地に送ることにします。

そうすると、なんと、番地の順にデータが整列しているではありませんか！

検証

gentle_stalin_sort.py

def gentle_stalin_sort(arr):
    siberia = [None] * int(max(arr) + 1)
    for n in arr:
        try:
            siberia[int(n)] = n
        except:
            pass  # siberiaに送れないnは粛清
    return [n for n in siberia if n is not None]  # n>0なら if n だけでよい


a = [5, 3, 4, 0, 2, 1]
gentle_stalin_sort(a)

すてき！

え？
Nが大きな値の時はどうするのか？
シベリアは広大なので、そんなことは気にしません。

計算量

やさしいスターリンソートのソースを見ると、一重のループしか存在しません。
実際、ちゃんと実装をすれば時間計算量のオーダーは O(len(arr) + max(arr)) で済みます。すごい！
ただし、空間計算量としてもmax(arr)という広大なシベリアの土地が必要になります。

自然数でないデータの取り扱い

では、0.183のように、自然数ではないデータが存在する場合、どのように扱うのがよいでしょうか。
粛清するのも手ですが、粛清をしないとすると、いくつかの方法が考えられます。

• 数値をN倍して、全体が自然数になるようにする。
• 小数点以下を切り捨てた値で「やさしいスターリンソート」をかけてから、重複した値についてはN倍して切り捨てるなどしてもう一度ソートをかける。

重複しているキーがある場合

粛清します

以下のように、シベリアに行く前に鉄道で準備をすることにより、回避することができます。
なお、int(n)は事前にarrに適用されているものとして省略しました（そうでないとmax(arr)を取れないので、バグっていました）

gentle_stalin_sort2.py

def gentle_stalin_sort(arr):
    # 鉄道の整備
    train = [0] * (max(arr) + 1)
    copy_train = [0] * (max(arr) + 1)
    for n in arr:
        copy_train[n] = train[n] = train[n] + 1
    # シベリアの大地の整備と、鉄道を利用した配置
    siberia = [[None] * max(train) for _ in range(max(arr) + 1)]
    for n in arr:
        train[n] -= 1
        siberia[n][train[n]] = n
    result_arr = [0 for _ in arr]
    # シベリアに並んだ人々を刈り取って直列にする
    current_position = 0
    for i in range(max(arr) + 1):
        for j in range(copy_train[i]):
            result_arr[current_position] = siberia[i][j]
            current_position += 1
    return result_arr

鉄道が増え、またシベリアの大地の重厚さが増しました。空間計算量がmax(arr) * len(arr)のオーダーになっています。
このリストの作り方だと、リストのリストになるのでPython的には重くなってしまうのですが、本質的にはこれは多重配列であって、きちんとndarray等で書くことにすればよいので、些末な部分と思うことにして詳細割愛します。
（つまり、Pythonにおいては早くないコードですが、適当に書き換えれば十分速くなります）

この計算についてですが、2重のループになっている箇所について、for j in range(copy_train[i]):のところはlen(siberia)回評価されますが、配列の生成方法からcurrent_positionが0 to len(arr)で動くので、結局オーダーをlen(siberia) + len(arr)に抑えることができます。¹

まとめ

ソートをするときには、心理的・物理的安全性を大事にしてシベリアの広大な大地を活用すると、犠牲者を出さずにソートできる。
みんな、やさしくなろう！

ネタバレ

一般的には、このソート方法は「バケツソート」と呼ばれています（特にバケツが沢山ある場合）
https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88

1. なので、Wikipediaの記事でなぜ英語も日本語も最悪時間計算量が$O(n^2)$と書かれているのかが分かっていません… ↩