Geben Sie die Laufzeitabschatzung fur den BubbleSort an. Begrunden Sie Ihre Antwort.
(Worst-Case) O(n)=n^2
(Average-Case) O(n)= n^2
(Best-Case) O(n)= n
Geben Sie die Laufzeitabschatzung fur den Quicksort an. Begrunden Sie Ihre Antwort.
(Worstcase) O(n)=n^2
Tritt ein, wenn bei jeder Pivotisierung das größe oder das kleinste Element gewählt wird
Best-Case:O(n*ld(n))
Average Case:O(n*ld(n))
Wie muss eine Liste sortiert sein, die mit Bubblesort aufsteigend sortiert werden soll sortiert sein für:
average …
worst …
best …
-case
Worst: absteigend sortiert
Average: unsortiert
Best: aufsteigend sortiert
Was passiert während der Ausführung des Quicksort-Verfahrens bei der Pivotisierung
Ein Pivotelement wird ausgesucht (zufällig, Mitte, Median)
Die Elemente werden bei aufsteigender Sortierung solange vertauscht, bis alle Elemente größergleich als pivot rechts von pivot sind und der rests links.
Was komplettiert das Quicksort verfahren nach dem Pivotisierungsschritt
Die rekursive Fortsetzung der Pivotisierung in den beiden Teillisten bis diese nur noch einelementig sind
Last changed9 months ago