Insertionsort und Selectionsort

Kurz: Insertionsort und Selectionsort sind einfache Sortierverfahren mit Laufzeit O(n²). Für kleine Datenmengen sind sie praktisch.

Genauer: Selectionsort sucht in jedem Durchlauf das kleinste restliche Element und stellt es nach vorn. Insertionsort nimmt nacheinander jedes Element und schiebt es an die richtige Stelle in den schon sortierten Teil, wie beim Sortieren von Spielkarten in der Hand.

Im Detail

• Insertionsort: Stabil, im besten Fall (fast sortiert) O(n), schnell bei kleinen Listen. Deshalb nutzen es viele Bibliotheken für kurze Teilstücke.
• Selectionsort: Wenige Vertauschungen (höchstens n−1), aber immer O(n²) Vergleiche.
• Stabil: Gleiche Elemente behalten ihre Reihenfolge.
• Vergleich: Bubblesort ist ähnlich einfach, aber meist langsamer. Für große Listen nimmt man Mergesort oder Quicksort.
• Beispiel Insertionsort: [5, 2, 4, 1] → [2, 5, 4, 1] → [2, 4, 5, 1] → [1, 2, 4, 5].

Siehe auch: Sortieren, Fortgeschrittene Sortierverfahren