Abituraufgaben: Sortierverfahren vergleichen

Umstellungen/Schreibzugriffe: wie oft Elemente vertauscht oder verschoben werden (ein Tausch schreibt zwei Plätze, eine Verschiebung einen). Speicherbedarf: ob zusätzlich zur Reihung Speicher nötig ist — alle drei arbeiten in-place mit einer Hilfsvariable. Stabilität: ob Elemente mit gleichem Wert ihre ursprüngliche Reihenfolge behalten. (Auch möglich: Verhalten bei vorsortierten Daten.)

B = Selectionsort: V ist bei jeder Eingabe \(\frac{1000\cdot999}{2}=499\,500\), und U bleibt immer unter \(n-1=999\). A und C brauchen vorsortiert nur \(n-1=999\) Vergleiche und haben stets gleich viele Umstellungen (jede behebt genau ein falsch geordnetes Paar). Bei zufälliger Eingabe vergleicht C nur etwa halb so oft wie A: Insertionsort bricht die Suche nach der Einfügestelle ab, sobald sie gefunden ist, während Bubblesort ganze Durchläufe ausführt. Also C = Insertionsort, A = Bubblesort mit Abbruch.

\(V(2000)=\frac{2000\cdot1999}{2}=1\,999\,000\). Allgemein \(V(n)=\frac{n^2}{2}-\frac{n}{2}\); für große n bestimmt der quadratische Term den Wert. Mit \(2n\) statt \(n\) wird daraus \(\frac{(2n)^2}{2}=4\cdot\frac{n^2}{2}\), also etwa das Vierfache (hier \(1\,999\,000:499\,500\approx4{,}002\)).

In Runde 1 ist das Minimum 1 ganz hinten; es wird mit der 1000 getauscht — damit stehen zwei Elemente richtig. Runde 2 tauscht 2 und 999 usw. Nach 500 Runden steht die Reihung sortiert; in den restlichen 499 Runden steht das Minimum schon vorn, es wird nicht getauscht. Also 500 Umstellungen.

Ada und Cem haben dieselbe Zeit 41. In der Ergebnisliste sollen sie in alphabetischer Reihenfolge stehen: Ada vor Cem. Ein stabiles Verfahren ändert die Reihenfolge gleicher Schlüssel nicht; da die Liste vorher alphabetisch war, bleibt Ada vor Cem. Ein instabiles Verfahren könnte Cem vor Ada setzen — die Liste wäre korrekt nach Zeit, aber nicht wie gefordert.

Runde 1: Minimum 36 (Dora, Index 3) wird mit Index 0 (Ada, 41) getauscht → Dora 36, Ben 38, Cem 41, Ada 41. Runde 2: Minimum 38 steht schon an Index 1. Runde 3: Vergleich 41 < 41 ist falsch, Cem bleibt vorn. Ergebnis: Dora 36, Ben 38, Cem 41, Ada 41. Cem steht vor Ada, obwohl Ada vorher vor Cem stand — der weite Tausch in Runde 1 hat Ada hinter Cem geworfen. Selectionsort ist also nicht stabil.

Stabil, weil nur bei zeiten[j] > aktZeit verschoben wird: ein Eintrag mit gleicher Zeit bleibt links vom einzufügenden. Bubblesort (Tausch nur bei >, beide Reihungen tauschen) ist ebenfalls korrekt. In Java wären zeiten und namen Parameter vom Typ int[] bzw. String[].

Selectionsort: ungeeignet — jede Neusortierung kostet \(\frac{3000\cdot2999}{2}\approx4{,}5\) Mio. Vergleiche, auch wenn nur ein Eintrag falsch steht; außerdem nicht stabil. Insertionsort: am besten — die ersten Elemente sind sortiert, jedes braucht nur einen Vergleich; der neue Eintrag wird von hinten an seinen Platz geschoben. Das kostet höchstens \(n-1\) Vergleiche plus die Verschiebungen bis zu seinem Platz, und es ist stabil. Bubblesort mit Abbruch: stabil und bei einer schwachen Zeit (Eintrag gehört ans Ende) schnell — ein Durchlauf ohne Tausch. Bei einer guten Zeit wandert der Eintrag aber pro Durchlauf nur einen Platz nach vorn; im schlimmsten Fall sind fast alle Durchläufe mit rund 4,5 Mio. Vergleichen nötig. Fazit: Insertionsort. (Noch besser wäre, den neuen Eintrag direkt einzufügen statt die ganze Liste neu zu sortieren.) Vollständig ist die Bewertung, wenn alle drei Verfahren nach Aufwand im konkreten Fall und nach Stabilität beurteilt werden.