Problem mit Prüfungsaufgabe (Sortieralgorithmus)

contable

Guten Tag

Habe in einer alten Prüfungsaufgabe folgenden Algorithmus zum Sortieren eines Arrays gefunden:

void sort (int a[], int b[], int N, ixit left, int right){
		int i,j,k,middle;
	        if(right-left) {
		    middle = (left+right)/2;
		    sort (a,b,N,left,middle);
		    sort (a,b,N,middle+1, right);
		    for (k=left; k<=right; k++) b[k]=a[k];
		    i=left;
		    j=middle+1;
		    for (k=left; k<=right; k++){
		        if (i>middle && j<=right) a[k]=b[j++];
		        if (j>right && i<=middle) a[k]=b[i++];
		        if (i<=middle && j<=right);
			    if (b[i]>b[j]) a[k]=b[j++];
			    else a[k]=b[i++];
	            }
                }
}

Nun ist die Frage, ob dieser Algorithmus stabil ist?

Dafür spiele ich ihn mit 4 Zahlen auf dem Papier durch.

2a, 1a, 1b und 2b

Komme dabei aber immer wieder zu dem Problem, dass ich irgend ein a[] mit b[5] oder irgendeiner anderen nicht definierten Zahl füllen möchte.

Falls jemand also Lust hat, ich könnte jede Hilfe gebrauchen.

Michael

PS: Die Musterlösung meint er sei stabil!

niemand

Ohne das jetzt intensiv durchzugehen, fällt mir auf, dass vermutlich es im unteren Teil der Hauptschleife so heissen sollte:

if (i<=middle && j<=right) {
   if (b[i]>b[j]) { a[k]=b[j++]; }
   else { a[k]=b[i++]; ]
}

Damit sollte dann eigentlich nicht mehr auf b[5] (wieso 5? b[4] ist auch schon falsch) zugegriffen werden können. (Vorausgesetzt Du startest mit left = 0, right = 3 in Deinem Beispiel). Dann sollten die if Abfragen verhindern, dass er über b[3] hinausgeht.
Der Algorithmus sieht jedenfalls recht wirr aus...

Mein Prof. ist eigentlich kein Fan von x[0], er findet das irgendwie unlogisch etwas mit 0 zu füllen, es sei denn er verwendet dieses Element als Sentinel. Noch zusätzlich kommt, dass es eine frage vorher heißt:

How many recursive of the function sort are generated if

1. N=2, left=2 and right=2 or
2. N=4, left=1 and right=4 or
3. N=2^n, left=1 and right =2^n

Das mit den Codeänderungen habe ich auch so verstanden. Habe leider beim copy&paste verfahren etwas schlampig gearbeitet, und nicht mehr geprüft ob alle Einrückungen vorhanden sind. Wobei natürlich stimmt, dass um die letzten zwei Befehle noch eine Geschweifte Klammer muss.

Trotzdem Danke!

Michael