選択ソートアルゴリズムが挿入のソートよりも一貫して高速なのはなぜですか？

Question

「ソートは、」私はランダムに生成されたリストに並べ替えを行うC＃WPFアプリケーションを設計して、それがかかった時間をミリ秒単位で出力していた整数

private void insertion_Click(object sender, EventArgs e) 
{ 
    Stopwatch sw = new Stopwatch(); 
    sw.Start(); 
    for(int i = 1; i < Sorted.Length; i++) 
    { 
     int j = i; 
     while(j>0 && Sorted[j-1] > Sorted[j]) 
     { 
      swap(Sorted, j - 1, j); 
      j -= 1; 
     } 
    } 
    sw.Stop(); 

    IsSorted = true; 
    UpdateButtons(IsSorted); 
    MessageBox.Show($"Insertion sort took {(sw.ElapsedMilliseconds).ToString()} milliseconds", "Insertion sort"); 
} 


//Selection sort 
private void selection_Click(object sender, EventArgs e) 
{ 
    Stopwatch sw = new Stopwatch(); 
    sw.Start(); 
    for(int i = 0; i < Sorted.Length-1; i++) 
    { 
     int CurrMinIndex = i; 
     for(int j = i; j < Sorted.Length; j++) 
     { 
      if(Sorted[j] < Sorted[CurrMinIndex]) 
      { 
       CurrMinIndex = j; 
      } 
     } 

     if(CurrMinIndex != i) 
     { 
      swap(Sorted, CurrMinIndex, i); 
     } 
    } 
    sw.Stop(); 

    IsSorted = true; 
    UpdateButtons(IsSorted); 
    MessageBox.Show($"Selection sort took {(sw.ElapsedMilliseconds).ToString()} milliseconds", "Selection Sort"); 
} 

のランダムに生成され、最初は未ソート配列でありますコンプリート。私は、挿入ソートは平均して選択ソートより優れているはずですが、私の結果はそうでなければ教えてくれます。私は一度、挿入ソートのタイミングが選択ソートに近づいたことを一度も見ていない。実際、私の選択ソートアルゴリズムは一貫して2倍速いようです！誰もがここで問題を見ていますか？私は2つのアルゴリズムのかなり一般的な形をしたと思ったが、私は誤って最適化したのだろうか？

編集：ここでは、私は私のリストを移入するために使用していたアルゴリズムは次のとおりです。

Sorted = new int[ListSize]; //initialize/populate unsorted array 
Random Rand = new Random(); 
for (int i = 0; i < ListSize; i++) 
{ 
    Sorted[i] = Rand.Next(-1000, 1000); 
} 

Answer 1

あなたの挿入ソートの実装では十分ではありません。その後、P

 int j = i; 
    int P = Sorted[j]; 
    while(j>0 && Sorted[j-1] > P) 
     { 
      Sorted[j] = Sorted [j-1]; 
      j--; 
     }; 
    Sorted[j] = P;