[解決済み] Bogosort (a.k.a Monkey Sort)よりも悪いソートアルゴリズムはあるのか？[クローズド］

質問内容

今朝は同僚とソートアルゴリズムについて議論し、大学時代にタイムスリップしたような気分になりました。 私たちは、次のようなお気に入りのものを思い出していました。 バカソート というソートアルゴリズムを見たことがあると、一人が言っていました。 O(n!) . それを見て、私は最悪のソートアルゴリズムを探し始めたんです。

完全にランダムなソートはかなりまずいだろうと仮定して（つまり、要素をランダムに並べる - 順番に並んでいるか？ いいえ、もう一度ランダムに並べる）、いろいろ調べてみると、どうやらそれは BogoSort、またはモンキーソート、または単にランダムソート .

Monkey Sort の最悪のパフォーマンスは O(∞) で、最良の場合は O(n) であり、平均性能は O(n·n!) .

現在公式に認められている、平均ソート性能が最悪のソートアルゴリズムは何でしょうか？ O(n·n!) )?

解決方法は？

から デビッド・モーガン・マー の「Esoteric Algorithms」のページ。 インテリジェント・デザイン・ソート

紹介文

インテリジェント・デザイン・ソートとは、「科学的根拠」に基づくソート・アルゴリズムである。 インテリジェント・デザイン

アルゴリズムの説明

元の入力リストが正確な順序で並んでいる確率は、1.5%である。 は1/(n!)である。この可能性は非常に小さいので、これは これは偶然に起こったことなので、きっとそうなんだろうというのは明らかに不合理です。 知的なソーターが意識的にその順序にしたものです。ですから すでに何らかの方法で最適にソートされていると考えてよいでしょう。 私たちの「昇順」に対するナイーブな理解を超越したものです。 その順番を私たちの先入観に合うように変えようとすると は、かえってソートされなくなる。

分析

このアルゴリズムは時間的に一定で、リストをインプレースでソートします。 追加メモリは一切必要ありません。それどころか 怪しげなコンピュータの技術は一切必要ない。ほめる ザ・ソーター!

フィードバック

ゲイリー・ロジャースが書いています。

ソートを時間的に一定にすることで は、ソーターの力を否定しています。その ソーターは時間の外側に存在するため ソートは時間を超越したものです。時間を必要とするのは を検証することは、その役割を弱めることになる。 ということです。したがって...この特別な ソートには欠陥があり、そのようなことはできません。 ソーター」に起因するものである。

異端！？