Python Merge Sort Anleitung

Das Sortieren von Daten ist eine der häufigsten Operationen, die Datenpraktiker in ihrer täglichen Arbeit durchführen. Oft müssen Daten in einer bestimmten Reihenfolge angezeigt werden, um sinnvolle Informationen zu extrahieren. Glücklicherweise müssen wir diese Aufgabe heutzutage nicht mehr manuell erledigen. Computer können die Magie für uns mit unschlagbarer Leistung vollbringen.

Es gibt mehrere Strategien zum Sortieren von Daten. In diesem Tutorial werden wir eine der effektivsten Sortiertechniken analysieren. Der „Merge-Sort“-Algorithmus verwendet eine Teile-und-Herrsche-Strategie, um ein unsortiertes Array zu sortieren, indem es zuerst in kleinere Arrays aufgeteilt wird, die später in der richtigen Reihenfolge zusammengeführt werden.

In den kommenden Abschnitten werden wir alle Details des Merge-Sort-Algorithmus diskutieren, wie er in Python aussieht, und einige praktische Tipps für eine reibungslose Implementierung geben.

Was ist Merge Sort?

Es gibt viele Sortieralgorithmen, aber es ist schwierig, einen zu finden, der besser funktioniert als Merge Sort. Nicht überraschend wird dieser Algorithmus in allen Arten von realen Anwendungen eingesetzt, wie der Sortierung großer Datenbanken oder der Organisation von Dateien auf einem normalen Computer.

Der Algorithmus basiert auf dem Teile-und-Herrsche-Paradigma, das in drei Teile unterteilt werden kann:

• Teilen: Dieser Prozess teilt das Problem in kleinere Teilprobleme auf.
• Herrschen: Die Teilprobleme werden rekursiv gelöst.
• Kombinieren: Die Lösungen der Teilprobleme werden kombiniert, um die endgültige Lösung zu erreichen.

Teile-und-herrsche-Strategie

Lass uns sehen, wie der Mergesort funktioniert. Angenommen, wir möchten die folgenden Zahlen sortieren, indem wir den Mergesort-Algorithmus anwenden. Der Algorithmus teilt die Daten rekursiv in zwei Teile und teilt weiter, bis jede Liste ein Element hat. Dann kombinieren wir sie, indem wir sie in eine andere Liste sortieren.

Problem des Mergesorts. Quelle: DataCamp

Zeit- und Raumkomplexität des Mergesorts

Es ist unmöglich, im Voraus zu wissen, welcher Sortieralgorithmus für ein bestimmtes Problem am besten geeignet ist. Es müssen mehrere Variablen berücksichtigt werden, die über den Algorithmus hinausgehen, einschließlich der Programmiersprache, die zum Schreiben des Codes verwendet wird, der Hardware, auf der sie ausgeführt werden, und den Besonderheiten der zu sortierenden Daten. 

Obwohl wir die genaue Laufzeit eines Sortieralgorithmus nicht vorhersagen können, können wir dennoch die Leistung verschiedener Sortieralgorithmen vergleichen, indem wir Zeit- und Raumkomplexität analysieren.

Zeitkomplexität des Mergesorts

Wie wir in einem separaten Leitfaden zur Big O-Notation und Zeitkomplexität erklärt haben, besteht das Ziel der Zeitkomplexitätsanalyse nicht darin, die genaue Laufzeit eines Algorithmus vorherzusagen, sondern zu bewerten, wie effizient ein Algorithmus ist, indem analysiert wird, wie sich seine Laufzeit ändert, wenn die Menge der Eingabedaten zunimmt.

Die Zeitkomplexitätsanalyse wird in der Big O-Notation geschrieben, einer mathematischen Notation, die beschreibt, wie schnell eine Funktion wächst oder abnimmt. Der Merge-Sort hat eine logarithmisch-lineare oder linearithmische Zeitkomplexität, die als O(N log(N)) notiert ist, wobei N die Anzahl der Elemente in der Liste ist. Der Buchstabe ‚O‘ steht für die ‚Ordnung‘ des Wachstums. 

In der Zeitkomplexitätsanalyse verhält sich die linearithmische Komplexität ungefähr ähnlich wie die lineare Komplexität, was bedeutet, dass die Ausführung direkt proportional zur Datenmenge sein wird. Wenn also die Datenmenge verdoppelt wird, sollte auch die Zeit, die der Algorithmus benötigt, um die Daten zu verarbeiten, verdoppelt werden, d.h., die Anzahl der Divisionen und Zusammenführungen wird sich verdoppeln.

Weil die Zeitkomplexität des Merge-Sortierens linear ist, bleibt seine Komplexität für die besten, durchschnittlichen und schlechtesten Fälle gleich. Das bedeutet, dass unabhängig von der Eingabereihenfolge der Algorithmus immer die gleiche Anzahl von Schritten benötigt, um abzuschließen.

Platzkomplexität des Merge-Sortierens

Zuletzt, neben der Zeit, die zur Beendigung der Aufgabe erforderlich ist, ist ein weiterer wichtiger Aspekt bei der Analyse der Algorithmuskomplexität die Schätzung, wie viel Speicher der Algorithmus benötigen wird, um zu vollenden, wenn das Problem größer wird.

Dies wird durch die Konzepte der Platzkomplexität und des Hilfsspeichers abgedeckt. Letzteres bezieht sich auf den zusätzlichen Speicher oder temporären Speicher, der von einem Algorithmus verwendet wird, während ersteres den Gesamtspeicher bezeichnet, der von dem Algorithmus in Bezug auf die Eingabegröße benötigt wird. Mit anderen Worten, die Platzkomplexität umfasst sowohl den Hilfsspeicher als auch den Speicher, der von der Eingabe verwendet wird.

Der Merge-Sort hat eine Platzkomplexität von O(N). Dies liegt daran, dass er ein Hilfsarray der Größe N verwendet, um die sortierten Hälften des Eingabearrays zusammenzuführen. Das Hilfsarray wird verwendet, um das zusammengeführte Ergebnis zu speichern, und das Eingabearray wird mit dem sortierten Ergebnis überschrieben.

Implementierung des Merge-Sort in Python

Lassen Sie uns den Merge-Sort-Algorithmus in Python implementieren. Es gibt mehrere Möglichkeiten, den Algorithmus zu kodieren; wir werden uns jedoch an die auf Rekursion basierte Methode halten, die wahrscheinlich am einfachsten zu verstehen ist und weniger Zeilen Code erfordert als andere Alternativen, die auf Iteration basieren.

Verständnis der Rekursion im Merge-Sort

Wenn Sie neu in dem Thema sind, tritt in der Programmierung Rekursion auf, wenn eine Funktion sich selbst aufruft. Schauen Sie sich unser Tutorial Verständnis rekursive Funktionen in Python an, um alles über diese leistungsstarken Funktionen zu erfahren.

Um den Merge-Sort zu implementieren, definieren wir zunächst den Grundfall: Wenn die Liste nur ein Element enthält, ist sie bereits sortiert, daher geben wir sofort zurück. Andernfalls teilen wir die Liste in zwei Hälften, left_half und right_half, und rufen merge_sort() rekursiv für jeden von ihnen auf. Dieser Prozess wird fortgesetzt, bis alle Unterlisten jeweils ein einzelnes Element enthalten.

Sobald wir diese sortierten Unterlisten haben, beginnen wir mit dem Verschmelzungsprozess. Dazu initialisieren wir drei Indexvariablen: i zum Verfolgen der Position in left_half, j für right_half und k für die endgültige verschmolzene Liste. Dann vergleichen wir Elemente aus beiden Hälften. Wenn das aktuelle Element in left_half kleiner ist, platzieren wir es in my_list[k] und bewegen i vorwärts. Andernfalls nehmen wir das Element aus right_half, platzieren es in my_list[k] und erhöhen j. Nach jedem Vergleich bewegen wir k vorwärts zur nächsten Position in der endgültigen Liste.

Dieser Prozess wird fortgesetzt, bis wir alle Elemente in einer der Hälften verglichen haben. Wenn noch Elemente in left_half oder right_half verbleiben, hängen wir sie direkt an die endgültige Liste an, um sicherzustellen, dass keine Daten zurückbleiben. Da der Merge-Sort rekursiv arbeitet, wird dieser Verschmelzungsprozess auf jeder Rekursionsebene ausgeführt, bis die gesamte Liste sortiert ist.

Python-Implementierung

Im Folgenden finden Sie den Code, der die unsortierte Liste des vorherigen Diagramms als Beispiel verwendet:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge Sort vs. Andere Sortieralgorithmen

Merge Sort ist ein ziemlich schneller Sortieralgorithmus, der besonders gut für große Datenbanken geeignet ist und oft als Benchmark für andere Algorithmen verwendet wird. Wenn es jedoch um kürzere Listen geht, tendiert seine Leistung dazu, niedriger zu sein als die anderer Sortieralgorithmen.

In der folgenden Tabelle finden Sie einen Vergleich von Merge Sort mit anderen beliebten Sortieralgorithmen.

Praktische Anwendungen von Merge Sort

Merge Sort hat eine hohe Leistungsfähigkeit beim Sortieren großer Listen, aber seine Effizienz nimmt ab, wenn es mit kleineren Listen arbeitet. Ebenso ist es in Szenarien, in denen bereits ein gewisser Grad an Ordnung in den Eingabelisten vorhanden ist, weniger effizient, da Merge Sort unabhängig von der Reihenfolge der Liste die gleichen Schritte ausführt.

Ein großartiger Anwendungsfall, in dem Merge Sort besonders nützlich ist, sind verkettete Listen. Eine verkettete Liste ist eine Datenstruktur, die aus einer Verbindung von linear miteinander verknüpften Knoten besteht. Jeder Knoten enthält die Daten und den Link, um sich mit dem nächsten Knoten zu verbinden.

Merge Sort wird für verkettete Listen bevorzugt, da er nur sequentiellen Zugriff auf Daten erfordert, was gut zur Natur verketteter Listen passt. Außerdem ist Merge Sort ein stabiler Sortieralgorithmus (d. h. er erhält die relative Reihenfolge gleicher Elemente in der sortierten Ausgabe), was bei der Aufrechterhaltung der Ordnung verketteter Listen eine sehr wichtige Überlegung ist.

Gängige Fehler und Fehlerbehebung

Der Merge-Sort-Algorithmus ist ziemlich unkompliziert, und der Raum für Verbesserung im Code ist begrenzt. Sie können jedoch die Komplexität Ihrer Sortierstrategie erhöhen, indem Sie die Größe der Eingabedaten berücksichtigen.

Wir haben bereits festgestellt, dass Merge Sort besser mit größeren Datensätzen funktioniert. Für kleinere Datensätze können andere Sortieralgorithmen mit einer Zeitkomplexität von O(N^2), wie z. B. Insertion Sort, besser geeignet sein. In diesem Fall müssten Sie lediglich eine Größenschwelle festlegen, unterhalb derer Sie anstelle von Merge und Sort den Insertion-Sort-Algorithmus verwenden würden.

Ansonsten wäre es eine gute Idee, die Parallelisierung zu erkunden. Die Schritte des Merge-Sortierens können mit ausreichender Rechenleistung leicht parallelisiert werden, wodurch die zur Fertigstellung benötigte Zeit reduziert wird. Lesen Sie unseren CPU vs GPU-Guide, um mehr über paralleles Rechnen zu erfahren.

Fazit

Merge-Sortieren ist einer der effektivsten und beliebtesten Sortieralgorithmen, aber es gibt noch viel mehr in dem wunderbaren und ständig wachsenden Universum der Algorithmen zu lernen. Wenn Sie an den Details von Algorithmen interessiert sind, wie sie funktionieren und ihre damit verbundene Komplexität, Vorzüge und Nachteile, können Ihnen diese DataCamp-Ressourcen helfen, Ihr Lernen fortzusetzen:

• Einführung in den Kurs für Datenstrukturen und Algorithmen
• Python-Programmierfähigkeiten-Track
• Python-Daten-Grundlagen-Track
• Kurs für fortgeschrittenes Python
• Karrieretrack Data Analyst in Python
• Big O Notation und Zeitkomplexität