c++ Anzahl Zähler Vertauschungen/Vergleiche InsertionSort

Guten Tag,
ich habe ein Programm geschrieben, dass ein Array nach InsertionSort sortiert.
in der Aufgabe steht aber auch, dass man die anzahl der Vergleiche sowie der Vertauschungen ermitteln soll.

Ich habe verschiedene Überlegeungen angestellt, und auch einfach mal versucht die Zähler einzusetzten, aber ich konnte bisher nur die Anzahl der Vertauschungen ermitteln.

Wo und Wie muss ich den Zähler einbauen, damit er die Anzahl der Vergleiche ermittelt?

Hier der relevante Quellcode:

void insertionsort(int *sortier_array, int a) 
	{
		int index,index_klein,wert_klein;

		for(index=1; index<a; index++) 				// Funktion, mit der das gesamte Array einmal von links nach rechts durchlaufen wird 
			{
			  wert_klein=sortier_array[index]; 	    // in dem Sortier-Array wird der erste wert als sortiert angenommen, und dessen Position im Array als Ausgangspunkt angenommen

				for( index_klein=index; 
				sortier_array[index_klein-1] > wert_klein&&index_klein > 0; 
				index_klein-- )

						{ //ist der vorhergegangene Wert im Array kleiner
						sortier_array[index_klein] = sortier_array[index_klein-1]; //wird er an den Anfang gesetzt.
						z++; //Zähler für die Anzahl der Vertauschungen
						}

			  sortier_array[index_klein]=wert_klein; //Die Position wird aktualisiert
			}
	}

cheopz

Das hängt schwer davon ab, wo du z deklarierst (was du gar nicht tust).

z ist als globale variable deklariert.

ich habe den restlichen quellcode wegelassen, um das Forum nicht zu überschwemmen

mir fällt gerade auf: Zähle ich nicht doch die Anzahl der Vergleiche gerade?

oO

cheopz

mir fällt gerade auf: Zähle ich nicht doch die Anzahl der Vergleiche gerade?

also ich habe es nochmal überprüft, es ist doch wie ursprünglich angenommen die Anzahl der Vertauschungen (die ja beim average case 0, und beim worst case ~ n²/2 ist)

Also zur ausgangsfrage: wie kann ich den zähler für die vergleiche einbauen?

cheopz

Du vergleichst in Zeile 10 (oder willst die Vergleiche in Zeile 5 auch dazuzählen? Ich denke nein). Also willst du zählen, wie oft du an Zeile 10 vorbeikommst.

Oder hab ich da was falsch verstanden?

zeile 5 dient nur dazu, das array einmal durchzulaufen.

hat keiner eine idee?

Th

Die Anzahl der Vergleiche und die der Vertauschungen ist bei deinem Sortieralgorithmus gleich, d.h. die Variable z gilt für beide.

Normalerweise unterscheidet man anhand folgender Sortiermethode (z.B. bei Bubble- oder Quicksort):

if(array[x] > array[y]) // Anzahl Vergleiche
{
  std::swap(array[x], array[y]); // Anzahl Vertauschungen
}

Hallo,
die Aussage stimmt nicht.
Als beispiel: Best Case, zahlen 1,2,3:
anzahl der vertauschungen wäre 0, aber 2 vergleiche.
ich habe jetzt das problem auf folgende art gelöst:

for(index=1; index<a; index++) 				// Funktion, mit der das gesamte Array einmal von links nach rechts durchlaufen wird 
			{
			  wert_klein=sortier_array[index]; 	    // in dem Sortier-Array wird der erste wert als sortiert angenommen, und dessen Position im Array als Ausgangspunkt angenommen

					[b]if(sortier_array[index_klein-1] < wert_klein&&index_klein > 0)
						{p++;};[/b]
				for( index_klein=index; 
				sortier_array[index_klein-1] > wert_klein&&index_klein > 0; 
				index_klein--)

						{ //ist der vorhergegangene Wert im Array kleiner
						sortier_array[index_klein] = sortier_array[index_klein-1]; //wird er an den Anfang gesetzt.
						z++; //Zähler für die Anzahl der Vertauschungen
						p++;
						}

			  sortier_array[index_klein]=wert_klein; //Die Position wird aktualisiert
			}

Vielen Dank für eure Ideen