皆さん、ソートは好きですか？
僕はHaskellerのクセにボゴソートが好きです。
ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる
— やんぎん (@4116You) July 28, 2019
なにやらTLでスターリンソートなるものが流行っていました。
まずO(n)とは何かという事なんですが、これはビッグ・オー記法と言ってアルゴリズムの性能の指標を表すものです。
O(n)の他にO(1)とかO(log(n))とかO(nlog(n))とかO(n^2)とかがありますが、詳しくは割愛します。この辺を参考にするとよく分かると思います。ともかく、O(n)はむっちゃ速い、というかソートアルゴリズムではまず有り得ないです。
にも関わらず、スターリンソートはその壁を打ち破って、O(n)で並べ替えを実現しちゃうんですよね。
というわけでHaskellで実装
StalinSort.hs
module StalinSort where
stalinSort :: Ord a => [a] -> [a]
stalinSort [] = []
stalinSort [x] = [x]
stalinSort (x : y : zs) | x < y = x : stalinSort (y : zs)
| otherwise = stalinSort (x : zs)
こんな具合です。
実行結果は以下の通り。
実行結果.hs
> stalinSort [1, 2, 1, 1, 4, 3, 9]
[1,2,4,9]
どうですか？見事にソートされてますね。
ん？ length xs == length $ stalinSort xs が False になる？
知りませんよそんな事。言うこと聞かない方が悪いんです。
追記
どうやら公式実装を見ていると、前の要素と同じ場合は粛清しないみたいですね。
てなわけで修正版↓
StalinSort.hs
module StalinSort where
stalinSort :: Ord a => [a] -> [a]
stalinSort [] = []
stalinSort [x] = [x]
stalinSort (x : y : zs) | x <= y = x : stalinSort (y : zs)
| otherwise = stalinSort (x : zs)
これ全部粛正すればO(1)では？ / “計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell - Qiita” https://t.co/1S47ZL781D
— ruichi (@ruicc) July 29, 2019
なるほど、確かにそうすればO(1)という画期的なソートアルゴリズムができますね！
StalinSort.hs
purgeAllStalinSort :: [a] -> [a]
purgeAllStalinSort _ = []
実行結果
実行結果.hs
> purgeAllStalinSort [1..100000]
[]
できましたね。