【要約】スターリンソートより酷いソートを作った ―― ポルポトソート [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
著者は、既存のジョークアルゴリズムよりも破壊的な手法を模索した。その結果、以下の特性を持つアルゴリズムが定義された。
- ・ソートとしての正当性が完全に欠如している。
- ・出力要素数の保証が一切存在しない。
- ・結果が確率に依存し、非決定的な挙動を示す。
// Approach
著者は、基準値による選別と、確率的な要素削除を組み合わせた。具体的な手順は以下の通りである。
1.配列からランダムに基準値を選択し、固定する。
2.基準値より大きい要素を、走査中に除外する。
3.生存要素に対し、一定の確率（デフォルト20%）でさらに除外を行う。
// Result
このアルゴリズムは、計算量の観点では極めて効率的である。実装の結果、以下の特性が確認された。
- ・計算量は最悪・平均・最良のすべてでO(n)である。
- ・PythonとJavaScriptの実装が提供されている。
- ・要素の消滅過程を可視化するスクリプトが同梱されている。
Senior Engineer Insight
> 実務への適用価値は皆無である。計算量O(n)は魅力的だが、出力の非決定性と正当性の欠如は、システム設計において致命的である。ただし、アルゴリズムの「酷さ」を可視化するツールとしての完成度は高く、ジョークとしての実装技術は評価できる。