Edited at

[ネタ] 要素数が変化しないO(n)のソートアルゴリズム


要素数が変化しないO(n)のソートアルゴリズム

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

上記アルゴリズムはO(n)時間でソートが完了する画期的なアルゴリズムである。ただし、つぎのような問題がある。

length xs == length $ stalinSort xsFalseになる」

今回紹介するのは、この問題を解決した修正版のアルゴリズムである。


追記

「タイトル詐欺はけしからん」との声がありましたので、マジメなほうを急遽作成しました。

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)時間でソートが完了し、かつ要素数が変化しない「洗脳ソート」を紹介した。