Einfügevergleich #s scheinen zu groß

Question

Ich bin verwirrt, wenn diese Vergleichszahlen so groß in Wert für einen Vektor mit 100 zufälligen zweistelligen Zahlen sein sollen. Volles Programm -> sicherer Link: https://ideone.com/oybDbD Die Programmausgabe befindet sich auf der unteren Seite des Links. Wertschätze schätzen.

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

Die durchschnittliche Leistung des Falles Insertionsort IS O(N^2) (die wiki entry sehen). Für Ihren Vektor aus 100 Elementen ist daher die erwartete Anzahl von Vergleichen O(10000). Wenn Sie mit 2656 oder in Ihrem zweiten Lauf mit 4995 auskommen, ist der Vergleich daher niedriger als, was Sie sonst erwarten würden.