Sortieralgorithmen: Einfügen, Auswahl und Mergesort

Ein Sortieralgorithmus bringt die Werte einer Liste in eine feste Reihenfolge, zum Beispiel vom kleinsten zum größten. Wie viele Schritte er dafür braucht, unterscheidet sich stark von Verfahren zu Verfahren.

Ein Onlineshop sortiert 100.000 Artikel nach dem Preis. Das eine Verfahren braucht dafür rund zehn Milliarden Schritte, ein anderes nur etwa 1,7 Millionen.

Sortieren durch Auswahl sucht in der Liste das kleinste Element und tauscht es an die erste Stelle. Dann sucht es das kleinste im Rest und tauscht es an die zweite Stelle, und so weiter.

Für n Werte vergleicht es immer (n minus 1), dann (n minus 2) und so fort. Das sind bei 5 Werten 4 + 3 + 2 + 1 = 10 Vergleiche, egal wie die Liste aussieht.

# Sortieren durch Auswahl: das Kleinste nach vorn holen.
preise = [7, 3, 9, 1, 5]
vergleiche = 0
for start in range(len(preise) - 1):
    kleinste = start
    for i in range(start + 1, len(preise)):
        vergleiche = vergleiche + 1
        if preise[i] < preise[kleinste]:
            kleinste = i
    # Das Kleinste tauscht den Platz mit dem Wert an der Startstelle.
    merke = preise[start]
    preise[start] = preise[kleinste]
    preise[kleinste] = merke
    print("Nach Runde", start + 1, ":", preise)
print("Vergleiche:", vergleiche)
# Machen Sie die Liste um drei Preise laenger. Wie viele Vergleiche sind es?

Sortieren durch Einfügen hält vorn einen sortierten Teil. Es nimmt den nächsten Wert und schiebt größere Werte eine Stelle nach rechts. In die Lücke kommt der neue Wert.

Ist die Liste schon fast sortiert, schiebt es kaum etwas. Ist sie umgekehrt sortiert, schiebt es jeden Wert ganz nach vorn.

# Sortieren durch Einfuegen: jeden Wert an die richtige Stelle schieben.
preise = [7, 3, 9, 1, 5]
for i in range(1, len(preise)):
    wert = preise[i]
    j = i - 1
    # Groessere Werte rutschen eine Stelle nach rechts.
    while j >= 0 and preise[j] > wert:
        preise[j + 1] = preise[j]
        j = j - 1
    preise[j + 1] = wert
    print("Nach dem Einfuegen von", wert, ":", preise)
# Probieren Sie [1, 3, 5, 7, 9] aus. Die while-Schleife laeuft dann nie.

Mergesort teilt die Liste in zwei Hälften und sortiert jede Hälfte auf dieselbe Weise, bis nur noch Listen mit einem Wert übrig sind. Eine Liste mit einem Wert ist schon sortiert.

Dann mischt es je zwei sortierte Listen zu einer. Beim Mischen schaut es nur auf die beiden vordersten Werte und nimmt den kleineren.

Auswahl und Einfügen haben zwei Schleifen ineinander und wachsen quadratisch: grob n mal n Schritte. Mergesort halbiert und mischt auf jeder Ebene alle n Werte einmal. Das sind grob n mal die Zahl der Halbierungen.

Bei 1000 Werten ist das 1.000.000 gegen 10.000 Schritte, also das Hundertfache.

Das Lab hat den Befehl sort. Er ordnet Zeilen, und mit -n ordnet er sie als Zahlen. Wir schicken dieselben fünf Preise wie in der Tabelle hinein.

paste -sd, setzt die Zeilen am Ende mit Kommas zu einer Zeile zusammen, damit Sie das Ergebnis auf einen Blick lesen.

printf "7\n3\n9\n1\n5\n" | sort -n | paste -sd,

printf "7\n3\n9\n1\n5\n" | sort -n -r | paste -sd,

printf "3\n1\n3\n2\n1\n" | sort -n -u | paste -sd,

Schreiben Sie mergesort(liste) mit Ihrer Funktion mische. Teilen Sie die Liste mit Slices in zwei Hälften, sortieren Sie jede Hälfte mit demselben Aufruf und mischen Sie die Ergebnisse.

Die Lektion über Rekursion erklärt, warum das funktioniert. Testen Sie schon jetzt mit [5, 2, 9, 1, 7].