Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

概要

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

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

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

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

スターリンソートでは、ソート順に反する要素を粛清することによりソートをしていました。
やさしいスターリンソートでは、粛清などという怖いことはしません。
代わりに、すべての要素をシベリアに送ります。大きいとか小さいとか関係ありません。皆平等にシベリア送りです。
ただし、シベリアに送る時に、データの値が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)$と書かれているのかが分かっていません… 

sasanquaneuf
座敷わらしになれる日を夢見て日々過ごしている一児の父です。 画像は「R」的なアレにインスパイアされて手書きで書いた「いぬ」です。 中学生の頃はVBなど。大学生の頃はC++ / Haskell / mathematica など。SIer時代はQlik Sense / R / C# / Java / PHP / JavaScript など。 最近は Python / TypeScript など。
https://qiitadon.com/@sasanquaneuf
uniaim
心と歴史を動かす。Tabレジ、Event Manager+、Point Manager、PREORDER、CASHIER等のサービス提供と、端末レンタル・イベント運営などを行っています。
https://uniaim.co.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした