sort ( int [ ] A, int l, int r) {
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!
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!
