Selectionsort: das nächste Minimum wählen

1. Eine Runde besteht aus der vollständigen Minimumsuche und genau dem anschließenden Positionstausch.
2. Es werden die Plätze 0 und 3 vertauscht; die anderen Plätze bleiben unverändert.

Das Minimum 2 steht an Index 3. Der abschließende Tausch von Index 0 und 3 ergibt [2, 3, 5, 7]. Der mittlere Rest wird noch nicht umgeordnet.

1. Nach Runde 1 bleibt Index 0 fest; die zweite Suche beginnt erst an Index 1.
2. Das zweite Restminimum ist 4, nicht 5; nur seine Position wird mit der linken Restgrenze vertauscht.

Runde 1 tauscht 8 und 1: [1, 6, 4, 8, 5]. In Runde 2 ist 4 das Restminimum an Index 2; der Tausch mit Index 1 ergibt [1, 4, 6, 8, 5].

1. Ein neuer Kandidat muss streng kleiner sein; Gleichheit reicht nicht.
2. Das zuerst gefundene Minimum steht an Index 1, nicht an Index 2.

Die erste 2 an Index 1 wird Kandidat. Die gleich große 2 an Index 2 ersetzt sie wegen des strengen Vergleichs nicht. Der Tausch 0/1 liefert [2, 4, 2, 3].

1. Speichere eine Position, nicht den kleinsten Wert selbst.
2. Vergleiche a[j] mit a[minimum] und aktualisiere minimum nur bei streng kleinerem Wert.

def index_minimum(a, start):
    minimum = start
    for j in range(start + 1, len(a)):
        if a[j] < a[minimum]:
            minimum = j
    return minimum

1. Die Positionen vor start bleiben unberührt, selbst wenn dort kleinere Werte stehen.
2. Prüfe den Leerfall zuerst; verschiebe den Tausch hinter die vollständige Minimumsuche.

def selection_runde(a, start):
    ergebnis = a.copy()
    if len(ergebnis) == 0:
        return ergebnis
    minimum = start
    for j in range(start + 1, len(ergebnis)):
        if ergebnis[j] < ergebnis[minimum]:
            minimum = j
    ergebnis[start], ergebnis[minimum] = ergebnis[minimum], ergebnis[start]
    return ergebnis

1. Die äußere Schleife legt die nächste fertige Position i fest; die innere sucht nur rechts davon.
2. Setze minimum zu Beginn jeder äußeren Runde wieder auf i und tausche erst nach der inneren Schleife.

def selection_sort(a):
    ergebnis = a.copy()
    for i in range(len(ergebnis) - 1):
        minimum = i
        for j in range(i + 1, len(ergebnis)):
            if ergebnis[j] < ergebnis[minimum]:
                minimum = j
        ergebnis[i], ergebnis[minimum] = ergebnis[minimum], ergebnis[i]
    return ergebnis

1. Betrachte, warum in jeder Runde genau das kleinste noch nicht festgelegte Element ausgewählt wird.
2. Die nächste Minimumsuche beginnt bei k und greift nicht mehr auf die fertigen Positionen als Tauschziele zu.

Jede Runde setzt das nächste Minimum an die nächste freie Position. Dadurch ist der Präfix sortiert und enthält die kleinsten Werte; nur der Rest bleibt noch zu bearbeiten.

1. Die erste Runde vergleicht den Startkandidaten mit den vier weiteren Elementen.
2. Addiere die schrumpfenden Anzahlen 4 + 3 + 2 + 1.

Die vier Runden benötigen 4, 3, 2 und 1 Wertvergleiche. Insgesamt sind das 10, unabhängig von den konkreten Werten.