search
LoginSignup
99
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

updated at

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell

皆さん、ソートは好きですか?
僕はHaskellerのクセにボゴソートが好きです。

なにやら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 xsFalse になる?
知りませんよそんな事。言うこと聞かない方が悪いんです。

追記

どうやら公式実装を見ていると、前の要素と同じ場合は粛清しないみたいですね。

てなわけで修正版↓

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)という画期的なソートアルゴリズムができますね!

StalinSort.hs
purgeAllStalinSort   :: [a] -> [a]
purgeAllStalinSort _ =  []

実行結果

実行結果.hs
> purgeAllStalinSort [1..100000]
[]

できましたね。

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
99
Help us understand the problem. What are the problem?