prev up next

Previous: Heapsort Up: Sortieren Next: Untere Schranke für Sortieren durch Vergleichen

Zusammenfassung von Laufzeit und Platzbedarf

  Best Average Worst zusätzlicher Platz
Selection Sort $O( n^2 )$ $O( n^2 )$ $O( n^2 )$ $O(1)$
Bubble Sort $O(n)$ $O( n^2 )$ $O( n^2 )$ $O(1)$
Merge Sort $O(n \cdot log~n)$ $O(n \cdot log~n)$ $O(n \cdot log~n)$ $O(n)$
Quick Sort $O(n \cdot log~n)$ $O(n \cdot log~n)$ $O( n^2 )$ $O(log~n)$
Heap Sort $O(n \cdot log~n)$ $O(n \cdot log~n)$ $O(n \cdot log~n)$ $O(1)$

Der lineare zusätzliche Platzbedarf beim Mergesort-Algorithmus wird verursacht durch die Methode merge, welche für das Mischen zweier sortierter Folgen ein Hilfs-Array derselben Größe benötigt.

Der logarithmische zusätzliche Platzbedarf beim Quicksort-Algorithmus wird verursacht durch das Zwischenspeichern der Intervallgrenzen für die noch zu sortierenden Array-Abschnitte, die jeweils nach dem Aufteilen anhand des Pivot-Elements entstehen.

Beispiel:

Sei ein Array gegeben mit insgesamt 16 Daten. Der initiale Aufruf von Quicksort wird versorgt mit den Arraygrenzen [0,15]. Folgende Sequenz von gespeicherten Intervallgrenzen entsteht:

[0,15]
[0,7][8,15]
[0,7][8,11][12,15]
[0,7][8,11][12,13][14,15]
[0,7][8,11][12,13]
[0,7][8,11]
[0,7][8,9][10,11]
[0,7][8,9]
[0,7]
[0,3][4,7]
[0,3][4,5][6,7]
[0,3][4,5]
[0,1][2,3]
[0,1]

Die maximale Ausdehung liegt bei einer Folge von jeweils halbierten Intervallgrenzen; davon gibt es logarithmisch viele.


prev up next
Previous: Heapsort Up: Sortieren Next: Untere Schranke für Sortieren durch Vergleichen