六角レンチです(唐突)
前回、色々なソートアルゴリズムを実装しました。
公開してから反応たくさんもらえてうれしいです。
ところで
スターリンソートというのをご存知でしょうか？
自分は兄にO(n)のソートアルゴリズムとして教えられて知りました
この記事にスターリンソートの事が書いてあります。
仕組みとしては
- ソート対象のリストをどんどん見ていく
- もし、データがソートできていない(今の要素と比べて右の要素の方が小さい)時、そのデータを粛清し、なかったことにする
- 最後まで見たら返す。
- なんとソートできている！
...といった感じ。
とりあえず、文字だけだと仕組みがわかりずらいのでpythonで書いてみます(結局文字じゃん)
普通のスターリンソート
def stalinsort(target:list):
notsyukusei = [target[0]]
siberia = []
for i in target[1:]:
if i < notsyukusei[-1]:
# シベリア送り
siberia.append(i)
else:
# 粛清回避
notsyukusei.append(i)
return notsyukusei
まずは試運転してみましょう
ソートするリストを[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]として入れてみます。
[1, 8, 9]
なんということでしょう
要素の数が3個になってしまいました。
要素が減ってしまうのはソートとして嫌ですね
...ところで、シベリアはどうなっているのでしょうか？
シベリアを確認してみる
少し改造して、シベリアのリストも返すようにします。
(具体的には、return notsyukuseiをreturn notsyukusei, siberiaに)
もう一度[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]を入れてみます...
([1, 8, 9], [6, 1, 1, 3, 7, 1, 8])
右がシベリア送りされた数字たちです。
...これ再帰的にスターリンソートすれば、それぞれソートできるのでは？
シベリア送り祭り
要はシベリア送りしたものをもう一度招集し、またシベリア送りしてまた招集しなおし...ということ。
こんな感じ
def stalinsort(target:list):
if len(target) <= 1:
return target
else:
notsyukusei = [target[0]]
siberia = []
for i in target[1:]:
if i < notsyukusei[-1]:
# シベリア送り
siberia.append(i)
else:
# 粛清回避
notsyukusei.append(i)
return notsyukusei, stalinsort(siberia)
もう一度[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]を入れてみます
実行してみると...
([1, 8, 9], ([6, 7, 8], ([1, 1, 3], [1])))
なんか括弧だらけで気持ち悪いですが、とりあえずそれぞれソートできています。
ここで、よく見てみると括弧にはそれぞれ二つの要素が存在しています
二つの要素をどんどん合成していけたらソートできそうです。
...合成(マージ)？
スターリン・マージソート
ということで、今日の主役であるスターリン・マージソートです。
（いい名前思いつかなかった）
簡単にマージソートの動きを説明すると
- ソート対象のリストを分割する
- ソート済みのリストを合成していく
この二つで動いています
ここで、ソート対象のリストを分割する際マージソートでは二分割していますが、このスターリンソートを使っても分割できそうです
(マージしてるからこれただのマージソートだろっていうのはなし)
ということで作りました。
def stalin_mergesort(target:list):
# スターリン・マージソート
def _merge(rlist:list, llist:list) -> list:
returnlist = []
rindex = 0
lindex = 0
while rindex != len(rlist) and lindex != len(llist):
if rlist[rindex] >= llist[lindex]:
returnlist.append(llist[lindex])
lindex += 1
else:
returnlist.append(rlist[rindex])
rindex += 1
returnlist.extend(rlist[rindex:])
returnlist.extend(llist[lindex:])
return returnlist
if len(target) <= 1:
return target
else:
notsyukusei = [target[0]]
siberia = []
for i in target[1:]:
if i < notsyukusei[-1]:
# シベリア送り
siberia.append(i)
else:
# 粛清回避
notsyukusei.append(i)
return _merge(notsyukusei, stalin_mergesort(siberia))
_merge関数がマージソートの合成の部分。
下のif-else文が先ほどの再帰的なスターリンソートです。
どんな感じで動くのか気になる人向け
def stalin_mergesort(target:list):
# スターリン・マージソート
def _merge(rlist:list, llist:list) -> list:
returnlist = []
rindex = 0
lindex = 0
while rindex != len(rlist) and lindex != len(llist):
if rlist[rindex] >= llist[lindex]:
returnlist.append(llist[lindex])
lindex += 1
else:
returnlist.append(rlist[rindex])
rindex += 1
returnlist.extend(rlist[rindex:])
returnlist.extend(llist[lindex:])
print(returnlist)
return returnlist
if len(target) <= 1:
return target
else:
notsyukusei = [target[0]]
siberia = []
for i in target[1:]:
if i < notsyukusei[-1]:
# シベリア送り
siberia.append(i)
else:
# 粛清回避
notsyukusei.append(i)
print(notsyukusei, siberia)
return _merge(notsyukusei, stalin_mergesort(siberia))
printを付けてわかりやすくしました
[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]を引数として実行すると、出力は下になる
[1, 8, 9] [6, 1, 1, 3, 7, 1, 8]
[6, 7, 8] [1, 1, 3, 1]
[1, 1, 3] [1]
[1, 1, 1, 3]
[1, 1, 1, 3, 6, 7, 8]
[1, 1, 1, 1, 3, 6, 7, 8, 8, 9]
前半3個がスターリンソート、後半3個がマージソートの合成(マージ)。
前半3個を順を追って見ていくと
-
[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]をスターリンソートし、[1, 8, 9]と[6, 1, 1, 3, 7, 1, 8]を分離 -
[6, 1, 1, 3, 7, 1, 8]をスターリンソートし、[6, 7, 8]と[1, 1, 3, 1]を分離 -
[1, 1, 3, 1]をスターリンソートし、[1, 1, 3]と[1]を分離 - [1]はリストの長さが1以下なので、そのまま返す(ソート済み)
後半三個も同様に見ていくと
-
[1]と[1, 1, 3]を合成し、[1, 1, 1, 3]を作成 -
[1, 1, 1, 3]と[6, 7, 8]を合成し、[1, 1, 1, 3, 6, 7, 8]を作成 -
[1, 1, 1, 3, 6, 7, 8]と[1, 8, 9]を合成し、[1, 1, 1, 1, 3, 6, 7, 8, 8, 9]を作成 - ソート完了
といった感じに動く
試運転
もう一度、[1, 8, 6, 1, 1, 3, 7, 1, 9, 8]を入れてみます...
[1, 1, 1, 1, 3, 6, 7, 8, 8, 9]
ちゃんとソートできてますし、要素の数が減っていません
速度測定
ソートできるならやることは一つ。速度を測ります
環境
- CPU Core i7 4770
- OS Windows 10
- Python 3.9.6
測定方法
前回の記事と同じく、
ランダムなリストの生成には下の関数を使います
def random_list_gen(num:int, maxnum:int = 9) -> list:
import random
return [random.randint(0, maxnum) for _ in range(num)]
引数として、要素の数、上限値を受け取ってランダムな数字のリストを返す感じの関数です
maxnumを10000000に固定して要素の数を変化させながら測定します
また、このリポジトリにスターリン・マージソートとこの速度測定で使ったプログラムが置いてあります
speedtest.pyの一番下のtarget = profiles[1]みたいなところをtarget = profiles[7]に変更すれば同じ測定ができるはず
結果
縦軸は一回のソートにかかった時間、横軸は要素の数です。
上に行くほど遅くなり、下に行くほど速いです。
なので、遅いです。
ソートはできるようになりましたが遅いので実用性はないです
なんで遅いのかは知りません(そこまで調べるのはめんどくさそう)
ちなみに
さすがに選択ソートには勝てます
おまけ
haskellで書いてみました
ただreverse使ってるのであまりよくないかも
merge :: [Int] -> [Int] -> [Int]
merge n [] = n
merge [] n = n
merge (x:xs) (y:ys)
| x < y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
stalin :: [Int] -> [Int] -> [Int] -> ([Int], [Int])
stalin [] y siberia = (y, siberia)
stalin (x:xs) [] siberia = stalin xs [x] siberia
stalin (x:xs) (y:ys) siberia
| x < y = stalin xs (y:ys) (x:siberia)
| otherwise = stalin xs (x:y:ys) siberia
stalinmergesort :: [Int] -> [Int]
stalinmergesort [] = []
stalinmergesort [x] = [x]
stalinmergesort x = merge a b
where
c = stalin x [] []
a = reverse $ fst c
b = stalinmergesort $ reverse $ snd c