Sortieralgorithmen
Bubble, Insertion, Selection, Merge, Quick, Heap, Cocktail, Shellsort, Timsort, Introsort und Radix Sort als Balken-Animation mit Pseudocode-Highlight und Schritt-Log.
- Bubble SortBubble Sort interaktiv: Balken zeigen Vergleiche und Tausche jeder Runde, der Pseudocode die aktive Zeile. Mit Laufzeit in allen Fällen, Stabilität und Einsatz.
- Insertion SortInsertion Sort interaktiv: baut links einen sortierten Präfix auf und schiebt jedes neue Element an seinen Platz. Bestenfalls linear, sonst quadratisch, stabil.
- Selection SortSelection Sort interaktiv: Pro Runde wird das Minimum des unsortierten Teils an den Anfang getauscht. Genau n-1 Schreibvorgänge, immer O(n^2), nicht stabil.
- Merge SortMerge Sort interaktiv: rekursive Halbierung und stabile Verschmelzung mit L- und R-Puffer. Garantiert O(n log n), geeignet als External Sort für große Daten.
- Quick SortQuick Sort interaktiv: Pivot wählen, in kleinere und größere Werte partitionieren, rekursiv sortieren. Im Mittel O(n log n), im Worst Case O(n^2), in-place.
- Heap SortHeap Sort interaktiv mit Baumdarstellung: Max-Heap aufbauen, die Wurzel mit dem letzten Element tauschen, siftDown. Garantiert O(n log n) und in-place.
- Cocktail SortCocktail Sort (Shaker Sort) interaktiv: Bubble Sort in beide Richtungen. Löst das Schildkröten-Problem, im Worst Case O(n^2) und stabil.
- ShellsortShellsort interaktiv: Insertion Sort über weit entfernte Paare, deren Abstand schrittweise auf 1 sinkt. Mit der Standardfolge O(n^2) im Worst Case.
- TimsortTimsort interaktiv: Insertion Sort für kleine Runs und stabiler Bottom-up-Merge. Standard in Python und Java, O(n log n) im Worst Case und stabil.
- IntrosortIntrosort interaktiv: Quick Sort, der bei zu tiefer Rekursion zu Heap Sort wechselt und kleine Bereiche mit Insertion Sort sortiert. Garantiert O(n log n).
- Radix SortRadix Sort (LSD) interaktiv: stabiles Counting Sort je Stelle in Basis 10 mit 10 Buckets. Linear in O(d · n) für ganzzahlige Schlüssel fester Stellenzahl.
- Bogo SortBogo Sort interaktiv: mischt das Array per Fisher-Yates so lange, bis es zufällig sortiert ist. Erwartete Laufzeit O(n · n!), im Worst Case unbeschränkt.
Vergleich der Verfahren
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) | ja |
|---|---|---|---|---|---|
| Insertion Sort | O(n) | O(n2) | O(n2) | O(1) | ja |
| Selection Sort | O(n2) | O(n2) | O(n2) | O(1) | nein |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ja |
| Quick Sort | O(n log n) | O(n log n) | O(n2) | O(log n) | nein |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | nein |
| Cocktail Sort | O(n) | O(n2) | O(n2) | O(1) | ja |
| Shellsort | O(n log n) | O(n4/3) | O(n2) | O(1) | nein |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | nein |
| Radix Sort | O(d · n) | O(d · n) | O(d · n) | O(n + b) | ja |
| Bogo Sort | O(n) | O(n · n!) | O(∞) | O(1) | nein |