Eine Übersicht über gängige Sortieralgorithmen:
Vergleichsbasiert
| Name | Laufzeit | stabil | in-place | ||
|---|---|---|---|---|---|
| B | AVG | W | |||
| Selectionsort | $\Theta (n^2)$ | $\Theta (n^2)$ | $\Theta (n^2)$ | ✘[1] | ✔ |
| Bubblesort | $\Theta (n)$ | $\cal{O}(n^2)$ | $\Theta (n^2)$ | ✔ | ✔ |
| Insertionsort | $\Theta (n)$ | $\Theta (n^2)$ | $\Theta (n^2)$ | ✔ | ✔ |
| Quicksort | $\Theta (n \cdot \log(n))$ | $\Theta (n \cdot \log(n))$ | $\Theta (n^2)$ | ✘ | ✔ |
| Heapsort | $\cal{O}(n \cdot \log(n))$ | $\cal{O}(n \cdot \log(n))$ | $\cal{O}(n \cdot \log(n))$ | ✘ | ✔ |
| Mergesort | $\Theta (n \cdot \log(n))$ | $\Theta (n \cdot \log(n))$ | $\Theta (n \cdot \log(n))$ | ✔ | ✘[2] |
| Timsort | $\Theta (n)$ | $\cal{O}(n \cdot \log(n))$ | $\cal{O}(n \cdot \log(n))$ | ✔ | ✘ |
Ich habe - bis auf Timsort - jeden dieser Algorithmen in Python implementiert, siehe Python-Code für Sortieralgorithmen.
[1]: Beispiel: A = [2, 2, 1] [2]: in der Regel nicht in-place, kann aber auch in-place implementiert werden.
Nicht Vergleichsbasiert
Es sei
- $n$ die Anzahl der Zahlen,
- $d$ die maximale Anzahl der Stellen
- $k$ die Anzahl der möglichen Zeichen (die Basis).
Dann gilt:
| Name | Worst-Case Laufzeit | stabil | in-place |
|---|---|---|---|
| Radixsort | $\cal{O}(d \cdot (n+k))$ | ✔ | ✘ |
| Countingsort | $\cal{O}(n+k)$ | ✔ | ✘ |
Siehe auch
- Sorting Algorithm Animations: Eine tolle Website, die veranschaulicht, wie verschiedene Sortieralgorithmen funktionieren.
- What different sorting algorithms sound like
- Die Landau-Symbole