Wann einfache Sortierer

Einfache Verfahren lohnen bei kleinen n, Lehrzwecken und als Basisfall in Hybriden (z.B. Insertion in Quicksort-Blättern).

Für grosse n: $O(n \log n)$-Verfahren.

n sehr klein, fast sortiert, oder als Basisfall in Hybriden. Sonstwo: Arrays.sort / List.sort.

Vertiefung

Einfache quadratische Sortierer sind für kleine Arrays oft konkurrenzfähig, weil sie wenig Verwaltungsaufwand haben und lokal arbeiten. Insertion Sort eignet sich zusätzlich für fast sortierte Daten und als Abschluss kleiner Teilbereiche in hybriden Verfahren.

Selection Sort bietet eine vorhersagbar kleine Zahl von Elementbewegungen. Das kann auf Medien mit teuren Schreiboperationen relevant sein. Für grosse, ungeordnete Daten dominieren jedoch die vielen Vergleiche, sodass asymptotisch bessere Verfahren typischerweise gewinnen.

Schwierigkeitsstufen

1. Eingabegrösse und Vorsortierung als Auswahlkriterien erkennen.
2. Vergleichskosten von Schreibkosten unterscheiden.
3. Den Einsatz als Basisfall eines hybriden Sortierers begründen.

Fallstricke

Die Aussage "kleine Eingabe" hat keine universelle Grenze. Datentyp, Laufzeitumgebung, Cacheverhalten und Vergleichsfunktion beeinflussen den tatsächlichen Umschaltpunkt.