[解決済み] コンピュータサイエンスにおけるソートと実世界におけるソートの比較

質問

私はソフトウェアにおけるソートアルゴリズムについて考えていました。 O(nlogn) の障害を克服する可能性のある方法について考えていました。私は実用的な意味でより速くソートすることが可能だとは思っていませんので、私がそうだとは思わないでください。

とはいえ、ほとんどすべてのソート アルゴリズムで、ソフトウェアは各要素の位置を知っていなければならないようです。これは理にかなっており、そうでなければ、どのようにして、あるソート基準に従って各要素をどこに置くかを知ることができるでしょうか。

しかし、この考え方を現実の世界と照らし合わせてみると、遠心分離機は、密度によって分子を「ソート」するときに、各分子がどの位置にあるのかを知ることはできないのです。実際、遠心分離機は各分子の位置など気にもしていません。しかし、各分子が密度と重力の法則に従っているため、比較的短時間で何兆ものアイテムを並べ替えることができるのです。

各ノードのオーバーヘッド (各ノードに付加された何らかの値またはメソッド) を使用して、リストの順序を「強制」することは可能でしょうか? 遠心分離機のようなもので、各要素だけが空間内の相対的な位置 (他のノードとの関係) を気にするようなものです。あるいは、これは計算における何らかのルールに違反するのでしょうか？

ここで持ち上がった大きなポイントの1つは、自然の量子力学的効果と、それがどのようにすべての粒子に同時に並行して適用されるかということだと思います。

おそらく古典的なコンピュータは、本質的にソートを次のような領域に制限しているのでしょう。 O(nlogn) に制限されていますが、量子コンピュータはその閾値を越えて O(logn) アルゴリズムが並行して動作するようになるかもしれません。

遠心分離機が基本的に 並列バブルソート が正しいようで、これは時間複雑性が O(n) .

次に考えるのは、もし自然界が O(n) で分類できるのなら、なぜコンピュータにはできないのだろう？

どのように解決するのですか？

編集部: 遠心分離機のメカニズムを誤解していました。それは比較、それも大規模な平行移動を行うように見えます。しかし、2 つの特性を比較するのではなく、ソートされるエンティティの特性で動作する物理的なプロセスが存在します。この回答は、そのような性質のアルゴリズムをカバーしています。

遠心分離機は、要素間の比較によって実際に動作するのではなく、分離された個々の要素上の特性 (「遠心力」) によって実際に動作するソート メカニズムを適用します。 いくつかのソート アルゴリズムはこのテーマに該当し、特に 基数ソート . このソートアルゴリズムが並列化された場合、遠心分離機の例に近づくはずです。

他の非比較ソートアルゴリズムとしては バケットソート と カウントソート . バケットソートも遠心分離機の一般的な考え方に合うことがわかるかもしれません（半径がビンに相当する可能性があります）。

各要素が単独で考慮される、もうひとつのいわゆる「ソートアルゴリズム」は スリープソート . ここでは、遠心力ではなく時間がソートのために使用される大きさとして作用します。