挿入比較＃が大きすぎるようです

Question

これらの比較番号が100個のランダムな2桁の数字を持つベクトルの値が大きいと仮定すると混乱します。完全なプログラム - >安全なリンク：https://ideone.com/oybDbDプログラムの出力は、リンクの一番下のページにあります。入力を感謝します。

int insertionSort (vector<int> &v) { 
    int j, temp, counter = 0; 

    for (int i = 1; i < v.size(); i++) { 
     j = i; 

     while (++counter && j > 0 && v[j] < v[j-1]){ 
      temp = v[j]; 
      v[j] = v[j-1]; 
      v[j-1] = temp; 
      j--; 
     } 
    } 
    return counter; 
} 

Answer 1

挿入ソートの平均的な場合の性能は（wiki entry参照）O(N^2)あります。したがって、100要素のベクトルの場合、期待される比較数はO(10000)です。 2656で出てくるか、2回目の4995で比較するとはより低くなるでしょう。