Interaktive Demo
Insertionsort-Visualisierung
Insertionsort funktioniert wie das Sortieren von Spielkarten auf der Hand: Er nimmt ein Element nach dem anderen und fügt es an der richtigen Stelle in den sortierten Teil ein. Bei fast sortierten Arrays ist er sehr schnell.
Probiere „Fast sortiert“: Nur wenige Elemente müssen sich bewegen. „Umgekehrt“ ist der schlechteste Fall.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Unsortiertes Element
- Sortierter Teil
- Einzufügendes Element
- Verglichenes Element
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n)
Schon sortiert: Jedes Element braucht nur einen Vergleich, um zu bleiben, wo es ist.
Mittlerer Fall
O(n²)
Im Mittel rückt jedes Element an der Hälfte des sortierten Teils vorbei.
Schlechtester Fall
O(n²)
Umgekehrte Reihenfolge: Jedes Element muss am ganzen sortierten Teil vorbei.
Zusätzlicher Speicher
O(1)
Nur das einzufügende Element wird zur Seite gelegt.
Stabil
Ja
Elemente rücken nur an größeren vorbei, nie an gleichen.
In-place
Ja
Elemente werden innerhalb des Arrays verschoben.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
| 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 diese Seite | 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 |
1. Ein Element herausnehmen
Der sortierte Teil beginnt mit dem ersten Element. Das nächste Element wird herausgenommen, dadurch entsteht eine Lücke im Array.
2. Größere Elemente verschieben
Nach links durch den sortierten Teil wird jedes größere Element eine Stelle nach rechts in die Lücke geschoben. Die Lücke wandert dabei nach links.
3. Einfügen
Beim ersten Element, das nicht größer ist, fällt das herausgenommene Element in die Lücke. Bei fast sortierten Arrays passiert das fast sofort, deshalb nutzen viele schnelle Sortieralgorithmen Insertionsort für kleine Teile.