事前に並べ替えられたシーケンス内の特定の数の要素と、そのシーケンスの反転数またはピアソンの r を使用して、最適な並べ替えアルゴリズムを見つけることは可能ですか?
たとえば、事前に並べ替えられた一連の262143要素があります。
反転の最大量は、シーケンス内の要素の数によって提供されます (この仮定については、ここの 2 ページを参照(n(n-1))/2してください) 。したがって、この例の最大値は です。n34359345153
これで、事前に並べ替えられたシーケンスの反転の数は1299203725最大3.78%になります。私のピアソンの r は0.9941です。私の理解では、これは高い「ソート度」を持つ事前にソートされたシーケンスである必要があります (間違っている場合は修正してください)。
シーケンスの「並べ替え」を定義する方法として、反転の数と人の r への多くの参照を見つけましたが、要素と反転の数/ピアソンの r のどの並べ替えアルゴリズムが優先されるかについて、ある種の比較を取得できませんでした1。
ご協力いただきありがとうございます。