配列をソートするためのスワップの最小数を確認する

Question

異なる要素を持つ配列があれば、それをソートするために必要なスワップの最小数はいくらですか？

たとえば、アレイ[4, 2, 1, 3]は、少なくとも2回のスワップ（たとえば、4回と1回、次に4回と3回のスワップ）が必要です。

これは私のアプローチです：

B = sort(copy(A)) 
for i = 0 ... len(A) - 1 
    if A[i] != B[i] 
     find j such that A[j] == B[i] 
     swap(A[i], A[j]) 

は私のアプローチのcorrertですか？それを解決する別の方法がありますか？

Answer 1

スワップの最小数を見つけようとしているのか、それとも実際に配列をソートしようとしているのかによって異なります。

アレイをソートしようとしている場合、スワップの最小回数はそれをより速くソートするのに役立ちません。最適なソートアルゴリズムを見つけることで、より速くソートするのに役立ちます。一般に、O（n log（n））の複雑さを持つものを見つけることを意味します（配列が小さいか、またはメモリが大きな制約でない限り）。この問題の解決に役立つGoogleはあなたの友人です。

実際にソートすることなく、必要なスワップの最小数を見つけようとしているのであれば、選択ソートの変更があります。 1つ目の方法は最小値を見つけ、最初のインデックスでスワップし、2番目に小さいスワップを2番目のインデックスで探すなどです。

しかし、スワップの最小量を見つけることでソートが最適化されません。選択ソートはクイックソートよりも少ないスワップを持つかもしれませんが、選択ソートがどのインデクスをスワップするかを決定するのに時間がかかります。選択ソートの時間複雑度はO（n^2）です。

O（n^2）とO（n log（n））の違いは、見た目ほど些細なものではありません。その数が約1,000,000の場合、それは20,000,000〜1,000,000,000,000の差になる可能性があります。