挿入と選択ソートの比較とスワップ時間が等しいか？

Question

私のコードでは、私は挿入の並べ替えと選択ソートの比較をカウントし、時間をスワップします。しかし、私は彼らが比較とスワップで同等であることを見ました。 しかし、whileループを挿入に使用しました。そして私は選択のためのループのために使用することができます。 コードを見てください。

<?php 
$a = array(4,1,7,9,3,2,6,8,10,20,14,29,54,27,563,4,563,334,2,7,5,42,24); 
$num = sizeof($a); 


for ($i=0; $i < $num; $i++) { 
    echo "$a[$i] | "; 
} 
echo "<br>"; 


echo "<br>Selection<br>"; 

//selection sort 
$swap = 0; 
$com = 0; 
for ($inner=0; $inner < $num-1; $inner++) { 
    $min = $inner; 

    for ($i=$inner+1; $i < $num; $i++) { 

    if ($a[$i] < $a[$min]) { 
     $min = $i; 

    } 
    $com++; 

    } 
    $swap++; 
    $past = $a[$inner]; 
    $a[$inner] = $a[$min]; 
    $a[$min] = $past; 
} 


for ($k=0; $k < $num; $k++) { 
    echo "$a[$k] | "; 
} 

echo "Com : <span style='color:red;'>$com</span> "; 
echo "Swap :<span style='color:red;'> $swap</span> "; 



echo "<br>Insertion<br>"; 


$swap = 0; 
$com = 0; 

for ($out=1; $out < $num ; $out++) { 
    $temp = $a[$out]; 

    for ($i=$out; $i > 0; $i--) { 
     if ($a[$i-1] >= $temp) { 
      $a[$i] = $a[$i-1]; 
     } 
     $com++; 
    } 
    $a[$i] = $temp; 
    $swap++; 
} 

for ($k=0; $k < $num; $k++) { 
    echo "$a[$k] | "; 
} 

echo "Com : <span style='color:red;'>$com</span> "; 
echo "Swap :<span style='color:red;'> $swap</span> "; 




?> 

Now。あなたはどのように私は挿入の並べ替えは、任意のsitiuationの選択ソートよりも速いと言うことができますか？彼らはいつも私のコードでeuqalされます！ありがとう

Answer 1

今、私は2つのアルゴリズムのパフォーマンスをテストするためのフレームワークを持っていません...しかし、私たちは純粋な理論的観点からパフォーマンスの内訳を作ることができると思います。

SELECTION SORT

これは繰り返しソートされていない配列から最初の要素を選択し、残りのソートされていない要素と比較することからなります。 バブルソートに似ていますが、小さな要素を交換するのではなく、最小の要素インデックスを更新して、各繰り返しの最後に交換します。

INSERTION SORT

これはソートサブ配列を作成し、繰り返しその中に新しい要素を挿入します。以下のロジックに従います。

• ソートされたサブアレイとして最初の要素を取ります。
• 2番目の要素をソートされたサブ配列に挿入します（必要に応じてシフトします）。
• 3番目の要素をソートされたサブ配列に挿入します（必要に応じてシフトします）。
• 洗い流し、要素がなくなるまで繰り返します。時間複雑さの点で

結論

、ソート選択（~O(n^2)に変換される）は、常に(n * (n - 1))/2あります。 の挿入ソートは、最悪の場合の時間複雑度が(n * (n - 1))/2（選択ソートと同じ）であるため、より良いパフォーマンスを提供します。私が選択肢を与えられた場合、の挿入ソートアルゴリズムを選択しました。最悪のことはの選択ソートの同じ性能を得ることです。あなたはいつでもmicrotimeを使用して、どちらが最良の結果をもたらすかを確認するために両方のクイックベンチマークを実行することができます。