Zusammenfassung

Zusammenfassung

Aufwände der vorgestellten SortieralgorithmenO(N2)

  Cmin Caver Cmax Mmin Maver Mmax
Selectionsort O(N2) O(N2) O(N2) O(N) O(N) O(N)
Insertionsort O(N) O(N2) O(N2) O(N) O(N2) O(N2)
Bubblesort O(N) O(N2) O(N2) O(0) O(N2) O(N2)
Quicksort O(NlogN) O(NlogN) O(N2) O(0) O(NlogN) O(NlogN)
Heapsort* O(NlogN) O(NlogN) O(NlogN) O(NlogN) O(NlogN) O(NlogN)

* Der Heapsort ist ein nicht stabiles Sortierverfahren!

Bei der Betrachtung der Gesamtlaufzeit muss auch der Speicherplatzverbrauch berücksichtigt werden:

Gesamtlaufzeit
  Min Average Max Speicher
Selectionsort O(N2) O(N2) O(N2) O(1)
Insertionsort O(N) O(N2) O(N2) O(1)
Bubblesort O(N) O(N2) O(N2) O(1)
Quicksort O(NlogN) O(NlogN) O(N2) O(logN)
Heapsort O(NlogN) O(NlogN) O(NlogN) O(1)

Der Quicksort benötigt Speicherplatz der dem Logarithmus der zu sortierenden Anzahl der Werte abhängt. Die rekursiven Aufrufe benötigen zusätzlichen Platz zum Verwalten der Intervallgrenzen.

Stefan Schneider Tue, 05/03/2011 - 15:30