Sortieralgorithmus, Komplexität bestimmen

[JAVAsk]

sort ( int [ ] A, int l, int r) {

if (A[l] > A[r ]){​

exchange (A[l], A[r ]);​

}​

if (l < r -1){​

k:= (r-l +1) div 3;​

sort (A, l, r-k);​

sort (A, l+k, r);​

sort (A, l, r-k);​

}​

}

Aufgaben:
a) Bestimmen Sie für den gegebenen Sortieralgorithmus die Komplexitätsklasse Θ im Best-, Worst- und
Average-Case für den Aufruf sort(A,0,n-1) in Abhängigkeit von n, der Anzahl der zu sortierenden Elemente
aus dem Array A. Dabei verursacht ein Aufruf von exchange eine Kosteneinheit.
b) Der vorgestellte Algorithmus ist nicht stabil. Ändern Sie den Algorithmus so ab, dass er stabil wird.

Es wäre sehr nett, wenn mir jemand helfen könnte.
Vielen Dank im Voraus!🙂

 

[stg]

Du musst schon selbst anfangen und eigene Ideen / Lösungsansätze zeigen bei denen man ansetzen kann. Ansonsten gegen Entgeld in der Jobbörse posten...

 

[JAVAsk]

Du hast natürlich Recht, aber ich habe keine Ideen/Lösungsansätze. Wenn du mir keine Lösung schicken kannst, ist es auch Ok, wenn du mir ein paar Ideen gibst.
Vielen Dank im Voraus!!!

 

[stg]

Ihr habt in der Übung oder sonst wo doch bestimmt schon mal etwas ähnliches gemacht, z.B. für den Quicksort o.Ä.?!
Zur Vereinfachung kannst du zunächt annehmen, dass die Länge deines Arrays eine Potenz von 3 ist.