MINT lernen

Selectionsort

Wie bringt man eine Reihung in Ordnung, wenn man immer nur das kleinste Element nach vorn holt?

1

Das Kleinste nach vorn

An der Mensakasse wurden fünf Wartezeiten (in Minuten) notiert. Selectionsort (Sortieren durch Auswählen) ordnet sie aufsteigend.

  • Zwei Teile:links wächst der sortierte Teil, rechts schrumpft der unsortierte Teil; am Anfang ist alles unsortiert.
  • Eine Runde:im unsortierten Teil das Minimum suchen und mit dem ersten Element des unsortierten Teils tauschen.
  • Ergebnis:nach jeder Runde ist der sortierte Teil um ein Element länger; nach \(n-1\) Runden ist das letzte Element automatisch richtig.
  • In-place:sortiert wird in derselben Reihung — es wird keine zweite Reihung angelegt.
RundeiMinimum (Index)Tauschwartezeit danach
107 (3)[0] ↔ [3]7 | 12 41 34 25
2112 (1)—7 12 | 41 34 25
3225 (4)[2] ↔ [4]7 12 25 | 34 41
4334 (3)—7 12 25 34 41
  • Ohne Tausch:steht das Minimum schon vorn (Runde 2 und 4), ändert sich nichts — der sortierte Teil wächst trotzdem.

Klicke in jeder Runde das Minimum des unsortierten Teils an (oder wähle es mit den Pfeiltasten und Enter). Beobachte die Zähler — und vergleiche mit ▶, wie der Algorithmus selbst sucht.

Minimum markieren

Halte fest: Um das Minimum sicher zu finden, muss jedes Element des unsortierten Teils angesehen werden — in jeder Runde gibt es einen Vergleich weniger, egal wie die Zahlen liegen.

2

Algorithmus und Aufwand

Die äußere Schleife zählt die Runden, die innere sucht die Position des Minimums.

public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int minPos = i;                          // Kandidat für das Minimum
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[minPos]) {
                minPos = j;
            }
        }
        int hilf = a[i];                         // Tauschen mit Hilfsvariable
        a[i] = a[minPos];
        a[minPos] = hilf;
    }
}
  • Hilfsvariable:ohne hilf würde a[i] = a[minPos]; den alten Wert von a[i] überschreiben — er wäre verloren.
  • Vergleiche:Runde 1 vergleicht mit \(n-1\) Elementen, Runde 2 mit \(n-2\), …, die letzte Runde mit einem.
Herleitung:
\(V(n)=(n-1)+(n-2)+\ldots+2+1\)
| rückwärts addieren
Ein Summand pro Runde; darunter dieselbe Summe in umgekehrter Reihenfolge schreiben.
\(2\cdot V(n)=\underbrace{n+n+\ldots+n}_{n-1\ \text{Summanden}}\)
| zusammenfassen
Übereinanderstehende Summanden ergeben jeweils \((n-1)+1=n\), \((n-2)+2=n\), …
\(2\cdot V(n)=n\cdot(n-1)\)
| \(:2\)
Gauß-Trick: \(n-1\) Paare mit der Summe \(n\).
\(V(n)=\dfrac{n(n-1)}{2}\)
Ergebnis
Für \(n=5\) sind das \(10\) Vergleiche, für \(n=1000\) schon \(499\,500\).
  • Unabhängig:die Anzahl der Vergleiche hängt nur von \(n\) ab — auch eine schon sortierte Reihung kostet \(\frac{n(n-1)}{2}\) Vergleiche.
  • Vertauschungen:höchstens eine pro Runde, also höchstens \(n-1\).
  • Nicht stabil:aus 7A 7B 3 wird nach dem Tausch [0] ↔ [2] die Reihung 3 7B 7A — gleiche Werte können ihre Reihenfolge ändern.
Merke

Selectionsort: \(\dfrac{n(n-1)}{2}\) Vergleiche, höchstens \(n-1\) Vertauschungen, nicht stabil.

3

Allgemeine Hinweise

Position merken, nicht den Wert

Die innere Schleife merkt sich minPos, nicht nur den kleinsten Wert. Ohne die Position weiß man beim Tauschen nicht, woher das Minimum kommt.

Die äußere Schleife endet bei Länge − 2

Nach \(n-1\) Runden ist das letzte Element von selbst das größte. Eine zusätzliche Runde schadet nicht, vergleicht aber nichts mehr.

Mit < statt <= vergleichen

Mit < bleibt bei gleichen Werten das erste Minimum der Kandidat. Mit <= würde der Algorithmus unnötig oft umentscheiden.

Videos