Hallo,



ich möchte bei folgendem Algorithmus eine Laufzeit - Analyse für den worst-case durchführen!

[/color] [color=black]void xyzSort(unsigned long a[], unsigned long laenge) [/color] [color=black]{[/color] [color=black]l = 0; //Zeile 1[/color] [color=black]r = laenge -1; //Zeile 2[/color] [color=black]for(i = r; i>=l+1; i--) //Zeile 3[/color] [color=black]{[/color] [color=black]	 for(j=l;j<=i-1;j++) //Zeile 4[/color] [color=black]	 {[/color] [color=black]		 if(a[j] >= a[i]) //Zeile 5[/color] [color=black]		 {[/color] [color=black]			temp = a[i]; //Zeile 6[/color] [color=black]			a[i] = a[j]; //Zeile 7[/color] [color=black]			a[j] = temp; //Zeile 8[/color] [color=black]		 }[/color] [color=black]	 }[/color] [color=black]	}[/color] [color=black]}[/color] [color=black]

[/color]

kurze Eläuterung des Sortierprinzips dieses Algorithmus(nach meiner Interpretation):

Von übergebenem Array werden letztes und erstes Element miteinander verglichen. Falls das erste größer ist, werden beide vertauscht. Als nächstes wird das zweite Element mit dem letzten verglichen und gegebenfalls vertauscht, usw.... Die Sortierung erfolgt aufsteigend!



Zur Laufzeitanalyse: (Annahme: eine Zeiteinheit für jede Anweisung)
Laufzeit immer durch zwei abgetrennt:



Zeile: Zeiteinheit:

(1) Initialisierung l = 0 ||1

(2) Initialisierung r = laenge-1 ||1

(3) Initialisierung i=r ||1

letzter Vergleich(in Schleife) i >= l+1 ||1

-------------------------------------------------------------------------

Dekrementierung i-- ||1 (r - mal)

Vergleich i>= l+1 ||1

(4) Initialisierung j = l ||1

letzter Vergleich j <=i-1 ||1

-------------------------------------------------------------------------

Inkrementierung j++ ||1 (r - mal)

Vergleich j <=i-1 ||1

(5) Vergleich a[j] >= a[i] ||1

(6) Zuweisung(worst case) temp = a[i] ||1

(7) Zuweisung(worst case) a[i] = a[j] ||1

(8) Zuweisung(worst case) a[j] = temp ||1

-------------------------------------------------------------------------

6 * r + 4 * r + 2





Nach meiner Berechnung sollte die Laufzeit O(r²) sein! Die beider for - Schleifen haben jeweils O(r) und zusammen sollte dies doch O(r²) ergeben?

Ist dies so korrekt??



Danke

Christian