要素数が変化しないO(n)のソートアルゴリズム
計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell
上記アルゴリズムはO(n)時間でソートが完了する画期的なアルゴリズムである。ただし、つぎのような問題がある。
「length xs == length $ stalinSort xsがFalseになる」
今回紹介するのは、この問題を解決した修正版のアルゴリズムである。
追記
「タイトル詐欺はけしからん」との声がありましたので、マジメなほうを急遽作成しました。
O(n)時間でソートが終了するバケットソートをHaskellで実装する
考えかた
要素数が変化してしまうのは「粛正」してしまうからだ。そんな乱暴なことをする必要はない。言うことをきかないなら「洗脳」してしまえばいい。
コード
bwsort :: Ord a => [a] -> [a]
bwsort [] = []
bwsort [x] = [x]
bwsort (x : xs@(y : ys))
| x > y = x : bwsort (x : ys)
| otherwise = x : bwsort xs
> bwsort [3, 7, 5, 2, 9, 15, 1, 4, 8]
[3,7,7,7,9,15,15,15,15]
これならlength xs == length (bwsort xs)はTrueになる。
まとめ
O(n)時間でソートが完了し、かつ要素数が変化しない「洗脳ソート」を紹介した。