# Sortieralgorithmen im Überblick: zwölf Verfahren visualisiert

> Alle zwölf Sortierverfahren auf einen Blick, von Bubble, Insertion und Merge Sort bis Quick, Heap und Tim Sort, je mit Visualisierung, Pseudocode und Laufzeit.

Adresse: https://marckimmel.de/informatik/sortieralgorithmen
English version: https://marckimmel.de/en/informatik/sortieralgorithmen.md

Bubble, Insertion, Selection, Merge, Quick, Heap, Cocktail, Shellsort, Timsort, Introsort und Radix Sort als Balken-Animation mit Pseudocode-Highlight und Schritt-Log.

## Themen

- [Bubble Sort](https://marckimmel.de/informatik/sortieralgorithmen/bubble-sort.md): Bubble 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 Sort](https://marckimmel.de/informatik/sortieralgorithmen/insertion-sort.md): Insertion Sort interaktiv: baut links einen sortierten Präfix auf und schiebt jedes neue Element an seinen Platz. Bestenfalls linear, sonst quadratisch, stabil.
- [Selection Sort](https://marckimmel.de/informatik/sortieralgorithmen/selection-sort.md): Selection 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 Sort](https://marckimmel.de/informatik/sortieralgorithmen/merge-sort.md): Merge 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 Sort](https://marckimmel.de/informatik/sortieralgorithmen/quick-sort.md): Quick 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 Sort](https://marckimmel.de/informatik/sortieralgorithmen/heap-sort.md): Heap Sort interaktiv mit Baumdarstellung: Max-Heap aufbauen, die Wurzel mit dem letzten Element tauschen, siftDown. Garantiert O(n log n) und in-place.
- [Cocktail Sort](https://marckimmel.de/informatik/sortieralgorithmen/cocktail-sort.md): Cocktail Sort (Shaker Sort) interaktiv: Bubble Sort in beide Richtungen. Löst das Schildkröten-Problem, im Worst Case O(n^2) und stabil.
- [Shellsort](https://marckimmel.de/informatik/sortieralgorithmen/shell-sort.md): Shellsort interaktiv: Insertion Sort über weit entfernte Paare, deren Abstand schrittweise auf 1 sinkt. Mit der Standardfolge O(n^2) im Worst Case.
- [Timsort](https://marckimmel.de/informatik/sortieralgorithmen/tim-sort.md): Timsort 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.
- [Introsort](https://marckimmel.de/informatik/sortieralgorithmen/intro-sort.md): Introsort 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 Sort](https://marckimmel.de/informatik/sortieralgorithmen/radix-sort.md): Radix 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 Sort](https://marckimmel.de/informatik/sortieralgorithmen/bogo-sort.md): Bogo 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

| Verfahren | Best Case | Average Case | Worst Case | Zusatz-Speicher | Stabil |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | ja |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | ja |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | 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(n^2) | 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(n^2) | O(n^2) | O(1) | ja |
| Shellsort | O(n log n) | O(n^{4/3}) | O(n^2) | 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 |

## Weiter

- [Informatik](https://marckimmel.de/informatik.md)