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
- 4431 views