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:
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.
- Printer-friendly version
- Log in to post comments
- 4399 views