Posted at

「スターリンソート」を改善したオートクラシーソート

話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装したというネタがあったので乗っかります。

元ネタは


ソートされていない要素を削除(粛清)して、強引に昇順リストを生成


というものですが、率直に言ってスターリンはまだ甘いです。

まず、ソート結果にも複数の要素が含まれてるということは、変更を加えられて再度、ソートされていない状態になる可能性を残してしまいます。

さらに、そのような不完全さを残しているにも関わらず、これにはO(n)もの時間がかかってしまいます。

こんなことでは真の独裁は維持できません。

さて、どうしたものか。

ということで、困ったときはドラえもんです。

かの有名な「どくさいスイッチ」を参考にしましょう。

最後にのび太が1人になる(いや、まあ、現実にはごにょごにょなんですが)アレです。

はい、オートクラシーソート!

autocracySort :: [a] -> [a]

autocracySort [] = []
autocracySort (x:_) = [x]

print $ autocracySort [1, 2, 3]

-- => [1]
print $ autocracySort [9, 234, 23, 2, 1, 93]

いくつ要素が含まれていようが、最初の1要素だけを含んだリストを返します。

ソート結果が正しいことも簡単に確認できる完璧なソートです。

そして何と計算量オーダーはO(1)です。

print $ autocracySort [n * n | n <- [1..]]

-- => [1]

さらに何と無限リストも扱えます。

これなら無限に湧いてくる聞き分けのない市民がいても、安心して独裁生活を送れます。

では、みなさん、良い独裁ライフを!