Interaktive Demo
Sortieralgorithmen
Sechzehn Sortieralgorithmen, Schritt für Schritt animiert: von einfachen wie Bubblesort bis zu modernen Hybriden wie Fluxsort und Crumsort. Jede Seite zählt Vergleiche und Schreibzugriffe, so siehst du, wie schnell jeder wirklich ist.
Einfache Verfahren
Bubblesort
Tauscht Nachbarn, bis die größten Elemente ans Ende aufgestiegen sind.
- Bester Fall
- O(n)
- Mittlerer Fall
- O(n²)
- Schlechtester Fall
- O(n²)
Stabil: JaIn-place: Ja
Selectionsort
Wählt das kleinste übrige Element aus und tauscht es nach vorne.
- Bester Fall
- O(n²)
- Mittlerer Fall
- O(n²)
- Schlechtester Fall
- O(n²)
Stabil: NeinIn-place: Ja
Insertionsort
Fügt ein Element nach dem anderen in einen wachsenden sortierten Teil ein.
- Bester Fall
- O(n)
- Mittlerer Fall
- O(n²)
- Schlechtester Fall
- O(n²)
Stabil: JaIn-place: Ja
Shellsort
Insertion Sort über schrumpfende Abstände, Elemente machen zuerst große Sprünge.
- Bester Fall
- O(n log n)
- Mittlerer Fall
- ≈ O(n1.25)
- Schlechtester Fall
- O(n1.5)
Stabil: NeinIn-place: Ja
Bäume und Heaps
Treesort
Baut einen binären Suchbaum und liest ihn der Reihe nach aus.
- Bester Fall
- O(n log n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n²)
Stabil: JaIn-place: Nein
Tournamentsort
Trägt ein K.-o.-Turnier aus, in dem immer das kleinste Element gewinnt.
- Bester Fall
- O(n log n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: JaIn-place: Nein
Heapsort
Baut einen Max-Heap und verschiebt immer wieder sein Maximum ans Ende.
- Bester Fall
- O(n log n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: NeinIn-place: Ja
Smoothsort
Ein Heapsort über einen Wald von Leonardo-Heaps, der sich sortierten Eingaben anpasst, von Edsger W. Dijkstra.
- Bester Fall
- O(n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: NeinIn-place: Ja
Mischen
Mergesort
Teilt das Array in Hälften und mischt die sortierten Hälften zusammen.
- Bester Fall
- O(n log n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: JaIn-place: Nein
Patiencesort
Legt die Elemente wie beim Kartenspiel auf Stapel und sammelt dann die kleinste oberste Karte ein.
- Bester Fall
- O(n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: JaIn-place: Nein
Timsort
Findet die schon geordneten Teilfolgen (Runs) und mischt sie geschickt, von Tim Peters.
- Bester Fall
- O(n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: JaIn-place: Nein
Blocksort
Ein stabiler Mergesort ohne zusätzlichen Speicher, der durch das Verschieben ganzer Blöcke mischt.
- Bester Fall
- O(n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: JaIn-place: Ja
Partitionieren
Quicksort
Teilt das Array an einem Pivot auf und sortiert beide Seiten rekursiv.
- Bester Fall
- O(n log n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n²)
Stabil: NeinIn-place: Ja
Introsort
Quicksort, der zu Heapsort wechselt, wenn die Rekursion zu tief wird, von David Musser.
- Bester Fall
- O(n log n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: NeinIn-place: Ja
Fluxsort
Ein stabiler Quicksort, der in einen Zwischenspeicher partitioniert, von Igor van den Hoven.
- Bester Fall
- O(n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: JaIn-place: Nein
Crumsort
Ein In-place-Quicksort mit der Lücken füllenden Fulcrum-Partition, von Igor van den Hoven.
- Bester Fall
- O(n)
- Mittlerer Fall
- O(n log n)
- Schlechtester Fall
- O(n log n)
Stabil: NeinIn-place: Ja
Im Überblick verglichen
| Algorithmus | Bester Fall | Mittlerer Fall | Schlechtester Fall | Zusätzlicher Speicher | Stabil | In-place |
|---|---|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Nein | Ja |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Shellsort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | Nein | Ja |
| Treesort | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Patiencesort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Blocksort | O(n) | O(n log n) | O(n log n) | O(1) | Ja | Ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.