Wie würde ich wissen, ob die Zählerinkremente an der richtigen Stelle sind, um die Anzahl der Vergleiche ~ C++ zu verfolgen?

Question

// Frage gelöst. Ich bin verwirrt darüber, wo die Zähler hinzugefügt werden, um die Anzahl der Vergleiche zu melden. Es bleibt immer bei einer festen Nummer und verändert sich nie. Angenommen, der Vektor enthält bei jeder Ausführung des Programms zweistellige Zufallszahlen. //

Bearbeiten: Neue Frage. Ich bin mir nicht sicher, ob die Zählerinkremente an der richtigen Stelle sind oder nicht, um Sortierung und Auswahl sortieren zu können. -Code an einem sicheren Link eingefügt:http://ideone.com/Bk90du

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

for (i = 1; i < v.size(); i++) 
{ 
     temp = v[i]; 

     j = i-1; 
     while(temp < v[j] && j >= 0) 
     { 
      v[j+1]=v[j]; 
      j--; 
      counter++; // tracking # of comparisons. 

     } 
     v[j+1]=temp; 
} 
return counter; // return counter 
} 

Answer 1

Nach dem (jetzt gelöscht) Kommentar, das ist main():

int main() { 
    int numCount; 
    vector<int> myVector2(myVector); 
    insertionSort(myVector2); 
    cout << endl << endl; 
    cout << "Vector after Insertion Sort: "; 
    printVector(myVector2); 
    cout << endl << endl; 
    numCount = insertionSort(myVector2); 
    cout << "Number of comparisons: " << numCount; 

Sie sortieren den gleichen Vektor zweimal, und den Vergleich Zahl drucken des zweiten Sortierlaufs. Wenn der Vektor bereits sortiert ist, entspricht die Anzahl der Vergleiche der Anzahl der Elemente im Vektor, da keine Arbeit erforderlich ist.

Um die wahre Anzahl von Vergleichen zu bekommen, Ihre main() ändern:

int main() { 
    int numCount; 
    vector<int> myVector2(myVector); 
    numCount = insertionSort(myVector2); 
    cout << endl << endl; 
    cout << "Vector after Insertion Sort: "; 
    printVector(myVector2); 
    cout << endl << endl; 
    cout << "Number of comparisons: " << numCount; 

Answer 2

Ohne zu wissen, was sind Ihre Testfälle, es auf der Anzahl der Vergleiche zu kommentieren ist nicht möglich, sie auszuführen. Wenn alle Fälle ähnliche Attribute haben, ist es durchaus möglich, dass sich der Code so verhält, wie er sollte.

EDIT: das folgende als Reaktion auf die Behauptung von OP in Kommentaren hinzugefügt, dass die Testfälle Vektoren mit 100 zufällig erzeugten zweistelligen Elementen sind.

Wenn, wie Sie in Kommentaren gesagt haben, Ihre Testfälle Vektoren mit 100 zufälligen zweistelligen Werten enthalten, dann hängt der Wert von counter davon ab, wie "unsortiert" die Elemente sind (mit dem minimal möglichen Wert für die Anzahl der Elemente). Unter der Annahme, dass alle Ihre Testfälle die gleiche Größe haben, ist der einzige Wert, der counter gleich ist, dass die Vektoren ähnlich sortiert sind, BEVOR Sie Ihre Funktion aufrufen. Wenn beispielsweise alle Vektoren in aufsteigender Reihenfolge und mit derselben Größe vorsortiert sind, gibt jeder Testfall den exakt gleichen Rückgabewert zurück. Wenn alle Vektoren in absteigender Reihenfolge und mit derselben Größe vorsortiert sind, gibt jeder Testfall genau denselben Rückgabewert (wenn auch anders als der zurückgegebene Wert, wenn sie anfänglich in aufsteigender Reihenfolge vorliegen).

Aus diesem Grund glaube ich nicht Ihren Kommentar, dass die Testfälle zufällig sind. Sie sind wahrscheinlich in irgendeiner Weise vorsortiert (oder vielleicht teilweise sortiert). Zum Beispiel könnten Sie Ihre Funktion für jeden Testfall zweimal aufrufen und nur den Wert count nach dem zweiten Aufruf ausgeben, wenn der Vektor bereits vorsortiert ist (wenn sich Ihr Code so verhält, wie er sollte).

Ende bearbeitet

, dass die Variable counter in Ihrem Code sagte, wird die Anzahl der Male der Körper der while Schleife ausgeführt wird akkumulieren. Das hat nichts mit der Anzahl der durchgeführten Vergleiche zu tun, da im Rumpf dieser Schleife kein Vergleich durchgeführt wird. Es bezieht sich auf die Anzahl der Einfügungen, nicht auf die Anzahl der Vergleiche.

Wenn durch „Vergleich“, meinen Sie wollen temp < v[j] Auswertung des Ausdrucks (im Unterschied zu anderen Ausdrücken, wie i < v.size() oder j >= 0, die auch Vergleiche im Code genannt werden könnte), dann könnte man etwas betrachten wie

tun

while (++counter && temp < v[j] && j >= 0) 

und Entfernen der Inkrementierung von counter aus dem Schleifenkörper.

Da counter auf Null initialisiert wird, zählt dies die Anzahl der Messungen temp < v[j] wird ausgewertet (++counter wird immer ein Ergebnis ungleich Null ergeben). Beachten Sie, dass, da temp < v[j] falsch sein kann, die Anzahl der Berechnungen j >= 0 nicht gezählt wird.