Merge-Sortierung in Python

1. Verwendung von Rekursion zur Implementierung von Merge Sort in Python
2. Verwenden Iterative Merge Sort in Python

Merge Sort ist ein beliebter Sortieralgorithmus, der verwendet wird, um die Elemente einer beliebigen Datenstruktur zu sortieren. Dieses Tutorial behandelt den Merge-Sort-Algorithmus und wie man ihn in Python implementiert.

Merge Sort ist ein Paradebeispiel für den Divide-and-Conquer-Ansatz und wird verwendet, um große Datensätze zu sortieren. Der Algorithmus beginnt mit der Aufteilung der gegebenen Datenstruktur in zwei Teile und wiederholt dann den gleichen Vorgang auf beiden Hälften. Schließlich fügt es die Hälften wieder zusammen, um effizient sortierte Werte zu erhalten. Wir nennen es daher ein Paradebeispiel für den Teile-und-Herrsche-Ansatz.

Das Beste an diesem Algorithmus ist, dass er in allen drei möglichen Fällen (durchschnittlicher Fall, bester Fall und schlimmster Fall) eine konsistente Zeitkomplexität von O(nlogn) hat. Aufgrund dieser Tatsache gilt es allgemein als effizient und wird für große Datenmengen bevorzugt.

Wir werden nun sehen, wie der Merge-Sort-Algorithmus mit der Programmiersprache Python implementiert wird.

Verwendung von Rekursion zur Implementierung von Merge Sort in Python

Merge Sort wird in Python einfach mit Hilfe einer rekursiven Funktion implementiert.

Der folgende Code verwendet Rekursion, um die Zusammenführungssortierung in Python zu implementieren.

def m(left, right):
    if not len(left) or not len(right):
        return left or right

    result = []
    i, j = 0, 0
    while len(result) < len(left) + len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break

    return result


def msort(list):
    if len(list) < 2:
        return list

    middle = int(len(list) / 2)
    left = msort(list[:middle])
    right = msort(list[middle:])

    return m(left, right)


lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst)
print("\n")
print("Sorted List:")
print(msort(lst))

Der obige Code liefert die folgende Ausgabe:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

Code-Erklärung:

• Die gegebene Liste wird bei jedem rekursiven Aufruf in zwei Hälften links und rechts geteilt, solange nicht zwei benachbarte Werte erhalten werden.
• Die Funktion m() wird erstellt und verwendet, um die beiden Hälften, die ursprünglich im ersten Schritt geteilt wurden, zusammenzuführen.
• Die Funktion msort() führt den größten Teil des Teilungs- und Sortierungsteils der gegebenen Liste im Programm aus.

Verwenden Iterative Merge Sort in Python

Der iterative Merge-Sort-Algorithmus unterscheidet sich ein wenig von der allgemeinen rekursiven Methode, da erstere den Bottom-up-Ansatz verwendet, während letzterer den Top-to-Bottom-Ansatz verwendet. Der zeitliche Aufwand und die endgültige Antwort bleiben jedoch bei beiden Methoden genau gleich.

Darüber hinaus verwendet das rekursive Merge-Sort-Verfahren einen expliziten Hilfsstapel, während es bei der Implementierung des iterativen Merge-Sort-Algorithmus nicht erforderlich ist.

Der folgende Code verwendet den iterativen Merge-Sort-Algorithmus, um Merge-Sort in Python zu implementieren.

def msort(a):
    width = 1
    n = len(a)
    while width < n:
        l = 0
        while l < n:
            r = min(l + (width * 2 - 1), n - 1)
            m = (l + r) // 2
            if width > n // 2:
                m = r - (n % width)
            mer(a, l, m, r)
            l += width * 2
        width *= 2
    return a


def mer(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]

    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1

    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1


a = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(a)
msort(a)
print("Sorted List:")
print(a)

Der obige Code liefert die folgende Ausgabe:

Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]

Nachteile von Merge Sort

Obwohl Merge Sort sehr beliebt ist und als hocheffizient gilt, hat es in verschiedenen Fällen einige Nachteile, die unten erwähnt werden.

• Beim Umgang mit einem kleineren Satz von Datenstrukturen kann es vergleichsweise langsamer sein als die anderen verfügbaren Sortieralgorithmen.
• Zur Implementierung dieses Algorithmus wird zusätzlicher Speicherplatz benötigt.
• Der Algorithmus wird immer den gesamten Prozess durchlaufen, auch wenn die angegebene Datenstruktur bereits sortiert ist.