mardi 19 mai 2015
Sortieralgorithmus, Komplexität bestimmen
Posted on 10:28 by verona
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!:)
Sortieralgorithmus, Komplexität bestimmen
Categories: Komplexität bestimmen, Sortieralgorithmus
Inscription à :
Publier les commentaires (Atom)
0 commentaires:
Enregistrer un commentaire