Sortieren durch Aufteilen

Sortieren von Zahlen

Es gibt verschiedene Strategien zum Sortieren von Dingen wie zum Beispiel Zahlen. Die folgenden verschiedenen Strategien kennst du bestimmt vielleicht schon aus diesem Kapitel (2.3.2.3). Falls nicht, kannst du sie dir bei Bedarf dort nochmal genauer anschauen.

• Sortieren durch Einfügen: Wir gehen eine Liste an Zahlen nacheinander durch und fügen jede Zahl an die richtige Stelle in einer zweiten, zu Beginn leeren Liste ein.
• Sortieren durch Auswählen: Wie das Sortieren durch Einfügen, mit dem Unterschied, dass wir hier immer die kleinste (oder größte) Zahl suchen und die dann an den Anfang (bzw. das Ende) der zweiten Liste anfügen.
• Sortieren durch Aufsteigen (Bubblesort): Wir gehen die Zahlen in der Liste paarweise durch und vergleichen je zwei Zahlen miteinander. Wenn sie in der falschen Reihenfolge sind, tauschen wir sie. Das machen wir so oft, bis die ganze Liste sortiert ist.
• Sortieren durch Zerlegen: Wir teilen die Liste in kleinere Listen auf und sortieren die kleineren Listen einzeln für sich. Zum Schluss fügen wir die sortierten Listen zusammen.

Die letzte Strategie schauen wir uns jetzt nochmal genauer an. Also: anstatt eine Liste von Zahlen auf einmal zu sortieren, teilen wir die Liste in mehrere kleinere Listen auf und sortieren diese für sich. Dann müssen wir die Zahlen der beiden kleinen Listen nur noch in der richtigen Reihenfolge zusammenfügen.

Als Pseudocode könnte das Ganze so aussehen:

# Teile die Liste in zwei kleinere Listen auf 
# Sortiere die beiden Listen 
sortiere_erste_liste()
sortiere_zweite_liste()

# Zusammenfügen der sortierten kleineren Listen
fuege_sortierte_listen_zusammen()
return zusammengefuegte_liste

Diesem Sortieralgorithmus können wir jetzt noch einen Namen geben. Da wir die sortierten Teillisten zusammenfügen, auf englisch mergen, nennen wir den Algorithmus mergesort. Die Funktion, die uns die beiden kleinen Listen zusammenfügt, nennen wir dann noch merge. Wie wir die Liste aufteilen, ist im Grunde egal. Deshalb machen wir es uns möglichst einfach und teilen die Liste in der Hälfte auf.

Außerdem müssen wir uns noch überlegen, was wir im Basisfall machen, also wenn die Liste nur eine einzige Zahl enthält. Eine Liste mit nur einer Zahl ist automatisch sortiert, deshalb können wir in dem Fall die Liste einfach unverändert zurückgeben.

def mergesort(l):
    if (len(l) == 1): # Basisfall: Liste mit einem Element ist sortiert
        return l
    else:
        # Rekursionsschritt: Teile die Liste in zwei kleinere Listen auf
        erste_haelfte_sortiert = sortiere(erste_haelfte) 
        zweite_haelfte_sortiert = sortiere(zweite_haelfte) 
        
        # Zusammenfügen der sortierten kleineren Listen
        zusammengefuegte_liste = merge(erste_haelfte_sortiert, zweite_haelfte_sortiert)
        return zusammengefuegte_liste

Nun haben wir nur noch ein Problem: wie sortieren wir die beiden kleinen Teillisten? Im Endeffekt haben wir zwar nun die Größe des Problems halbiert, in dem wir die Liste halbiert haben, aber dadurch haben wir das Problem ja noch nicht gelöst. Dafür brauchen wir doch jetzt einen weiteren Sortieralgorithmus, oder?

Hier kommt die Rekursion ins Spiel: wir erinnern uns an das Prinzip der Magie der Rekursion: wir nehmen an, dass die Funktion für das kleinere Problem bereits funktioniert und rufen die Funktion mergesort rekursiv auf. Die Ergebnisse der rekursiven Aufrufe sind dann also zwei sortiere Listen, die dann von der merge Funktion vereinigt werden zum Endergebnis.

def mergesort(l):
    if (len(l) == 1): # Basisfall
        return l
    else:
        # Rekursionsschritt: Teile die Liste in zwei kleinere Listen auf
        # erste_haelfte = ...
        # zweite_haelfte = ...
        erste_haelfte_sortiert = mergesort(erste_haelfte) 
        zweite_haelfte_sortiert = mergesort(zweite_haelfte) 
        
        # Zusammenfügen der sortierten kleineren Listen
        zusammengefuegte_liste = merge(erste_haelfte_sortiert, zweite_haelfte_sortiert) 
        return zusammengefuegte_liste

Zum Schluss können wir uns noch ein paar Zeilen Code sparen, wenn wir nicht alles in Variablen zwischenspeichern und die Listen Namen etwas abkürzen:

def mergesort(l):
    if (len(l) == 1): 
        return l
    else:
        # l1 = ...
        # l2 = ...
        return merge(mergesort(l1), mergesort(l2)) 

Aufgabe

def merge (l1, l2):
    if (len(l1) == 0):
        return l2
    else:
        if (len(l2) == 0):
            return l1
        else:
            if (l1[0] < l2[0]):
                return [l1[0]] + merge(l1[1:], l2)
            else:
                return [l2[0]] + merge(l1, l2[1:])