Edited at

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


概要

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

スターリンといえば粛清、というような考え方によるソートです。

しかし、ちょっと待ってください。スターリンには粛清以外の選択肢もありました。

すなわち、シベリア送りです。

この記事では、粛清ではなくシベリア送りによる「やさしいスターリンソート」を実装し、データの量を減らすことなく、計算量を減らします。

それによって、銀河に平和をもたらします。

※このソートは、「スターリンソート」とは異なるのでご注意ください。


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

スターリンソートでは、ソート順に反する要素を粛清することによりソートをしていました。

やさしいスターリンソートでは、粛清などという怖いことはしません。

代わりに、すべての要素をシベリアに送ります。大きいとか小さいとか関係ありません。皆平等にシベリア送りです。

ただし、シベリアに送る時に、データの値が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_position0 to len(arr)で動くので、結局オーダーをlen(siberia) + len(arr)に抑えることができます。1


まとめ

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

みんな、やさしくなろう!


ネタバレ

一般的には、このソート方法は「バケツソート」と呼ばれています(特にバケツが沢山ある場合)

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)$と書かれているのかが分かっていません…