[GO] Führen Sie die Sortierimplementierung / Berechnungsmengenanalyse zusammen und experimentieren Sie in Python

Dieses Mal werde ich über das Zusammenführen von Sortieren (unter Verwendung von Split Governance) des Sortieralgorithmus sprechen. Der Sortieralgorithmus ist ein Algorithmus, der die Elemente in der Datenstruktur in aufsteigender oder absteigender Reihenfolge sortiert, und die Zusammenführungssortierung ist einer der am häufigsten verwendeten Algorithmen.

Erklärung des Algorithmus

Bei der Zusammenführungssortierung erfolgt die Sortierung im Wesentlichen mithilfe eines Arrays. Wie der Name schon sagt, wird das Array geteilt und dann gemischt. Während dieses Mischens werden wir jedes Element vergleichen und sortieren. Als Ergebnis erhalten Sie ein sortiertes Array.

Teilt

Suchen Sie beim Teilen zunächst den Wert in der Mitte des Arrays mit mid = (low + high) / 2. Wenn beispielsweise die Länge des Arrays n ist, ist mid = (0+ (n-1)) / 2 der mittlere Wert und wird in zwei Arrays von 0 bis mid und mid + 1 bis n-1 unterteilt. Wird wiederholt und die Teilung endet, wenn die Länge des Arrays 1 wird. Bei der Teilung wird jede Sequenz in zwei Sequenzen unterteilt, so dass eine lange Sequenz die übergeordnete und zwei kurze Sequenzen derselben Länge die untergeordneten Sequenzen sind, wie in der Bifurkationsstruktur. Stellen Sie sich vor, dies hätte eine log (n) -Baumstruktur mit einer Tiefe von 2 erstellt.

Führung

Beim Regieren werden die ersten Elemente der beiden untergeordneten Arrays verglichen und am Anfang der übergeordneten Liste platziert. Anschließend wird der Zugriffsindex der Liste, die das ausgewählte Element enthält, um eins erhöht, das zweite Element mit dem ersten Element von eins verglichen und im nächsten Index der übergeordneten Liste gespeichert. Der Wert des auf diese Weise ausgewählten Index wird erhöht, die Arbeit des Speicherns in der übergeordneten Liste wird bis zum letzten Element einer der untergeordneten Listen wiederholt, und die Elemente der Liste mit den verbleibenden Elementen werden der Reihe nach gespeichert. Wenn Sie dies in der Reihenfolge vom Endknoten der Baumstruktur bis zum Wurzelknoten wiederholen, wird das nach dem letzten Wurzelknoten sortierte Array vervollständigt.

Am Ende werde ich eine Website veröffentlichen, die auf leicht verständliche Weise mit Grafiken erklärt wird.

Implementierung

Ich habe kurz eine Zusammenführungssortierfunktion implementiert, daher erkläre ich es. Ich habe die Zeilennummer von 1 in den Kommentar auf der rechten Seite jeder Zeile eingefügt.

merge_sort.py

def merge(array):                                   # line1
    mid = len(array)                                # line2
    if mid > 1:                                     # line3
        left = merge(array[:(mid/2)])               # line4
        right = merge(array[(mid/2):])              # line5
        array = []                                  # line6
        while len(left) != 0 and len(right) != 0:   # line7
            if left[0] < right[0]:                  # line8
                array.append(left.pop(0))           # line9
            else:                                   # line10
                array.append(right.pop(0))          # line11
        if len(left) != 0:                          # line12
            array.extend(left)                      # line13
        elif len(right) != 0:                       # line14
            array.extend(right)                     # line15
    return array                                    # line16

-Ich habe angenommen, dass der Wert, den der Parameter in Zeile 1 annimmt, ein Array ist, das nur Ganzzahlen im Element enthält.

-Ich habe mit line2 nach dem Wert der Länge des Arrays gefragt, aber es unterscheidet sich ein wenig von der obigen Erklärung, da ich jedes Mal ein neues Array erstellt habe, wenn ich es mit Python geteilt habe. Im Fall eines Arrays wie JAVA wird es geteilt, während die Indexnummer eines Arrays mit einem invarianten Objekt berechnet wird. Suchen Sie es also mit der oben beschriebenen Methode.

-In Zeile 3 wird beurteilt, ob die Länge des Arrays länger als 1 oder mehr ist. Wenn es lang ist, wird der Code von Zeile 4 bis Zeile 15 ausgeführt. Wenn er kurz ist, wird das Array so zurückgegeben, wie es als Rückgabewert ist.

-In den Zeilen 4 und 5 wird die Funktion aufgerufen, indem dem Parameter ein Array zugewiesen wird, das die übergeordnete Liste rekursiv in zwei Hälften teilt.

• Wie Sie bisher aus dem Code ersehen können, wird das Array durch rekursives Aufrufen der Funktion geteilt, bis es 1 wird.

-Der Grund, warum das übergeordnete Array in Zeile 6 leer ist, ist, dass die Methode append () (ein Element am Ende der Liste hinzufügen) verwendet wird, wenn danach ein Wert in die Liste eingefügt wird. Das ursprüngliche Array enthielt bereits einige Elemente, und ich dachte, es wäre unpraktisch, Elemente hinzuzufügen.

-Line7 hat eine Schleife verwendet, die jedoch weiterhin wiederholt wird, es sei denn, eine der Listen ist leer.

• Vergleichen Sie die ersten Elemente beider Arrays in den Zeilen 8 bis 11, löschen Sie das erste Element des Arrays mit kleineren Elementen und fügen Sie es am Ende des übergeordneten Arrays hinzu. Setzen Sie diesen Vorgang fort, bis eine der Listen leer ist.

-In den Zeilen 12 bis 15 wird eine Liste leer, wenn die Schleife von Zeile 7 endet, aber die andere Liste lässt mindestens ein Element übrig, sodass die verbleibenden Elemente beider Arrays in der übergeordneten Liste zusammengefasst werden. Zusätzlich zu.

• Geben Sie in Zeile 16 jedes sortierte Array als Rückgabewert zurück, sortieren Sie es in das übergeordnete Array jedes Arrays und geben Sie bei Erreichen des Stammknotens alle Elemente der Sequenz zurück, die dem Parameter in einem sortierten Zustand zugewiesen wurden. Ich werde.

Berechnungsbetrag

Sei T (n) der Gesamtbetrag der Berechnung in der Zusammenführungssortierung, wobei n die Anzahl der Elemente im Array oder die Länge des Arrays ist. Da T (0) und T (1) nichts tun, beträgt der Berechnungsbetrag 0. Bei der Zusammenführungssortierung wird das Array zuerst halbiert und die Zusammenführungssortierung wird rekursiv aufgerufen, sodass T (n / 2) dies zweimal mit dem Rechenaufwand (Zeile 4 und 5) tut, wenn es rekursiv aufgerufen wird, also T (n / 2). ) + T (n / 2) = 2T (n / 2) ist, wenn beide aufgerufen werden (Zeile 4 ~ 5). Darüber hinaus wird die Zusammenführungssortierung im schlimmsten Fall n-1-mal wiederholt, sodass der Gesamtbetrag der Berechnung T (n) = 2T (n / 2) + n-1 beträgt. Jetzt kennen Sie den Rechenaufwand, wenn die Länge des Arrays der Zusammenführungssortierung n beträgt. Da die Zusammenführungssortierung jedoch rekursiv aufgerufen wird, halbieren Sie das Array T (n / 2), T (n / 4), T. (n / 8) will ・ ・ ・ ・ ・ ・ ・ ・ Wir werden auch den Berechnungsbetrag prüfen, wenn T (n / (2 ^ (k-1))). k ist die Häufigkeit, mit der es rekursiv aufgerufen wird und bei k = 1 beginnt. T(n/2) = 2T(n/4) + n/2 - 1, T(n/4) = 2T(n/8) + n/4 - 1, T(n/8) = 2T(n/16) + n/8 - 1, ・ ・ ・ ・ ・ T(n/2^(k-1)) = 2T(n/2^k) + n/2^(k-1) - 1 Ist der Rechenaufwand bei k> = 1.

Einsetzen in die Gleichung von T (n) ergibt: T(n) = 2(2T(n/4) + n/2 - 1) + n - 1 = 4T(n/4) + 2n - (1 + 2) = 4(2T(n/8) + n/4 - 1) + 2n - (1 + 2) = 8T(n/8) + 3n - (1 + 2 + 4) = 8(2T(n/16) + n/8 - 1) + 3n - (1 + 2 + 4) = 8T(n/8) + 4n - (1 + 2 + 4 + 8) ・ ・ ・ ・ ・ = 2 ^ kT (n / 2 ^ k) + k * n- (1 + 2 + 4 + ・ ・ ・ ・ 2 + 2 ^ (k-1)) Es wird sein.

mit diesem T (n) = 0, wenn n = 0,1 T (n) = 2 ^ kT (n / 2 ^ k) + (k · n - k) - (1 + 2 + 4 + ・ ・ ・ ・ 2 + 2 ^ (k - 1)), Es stellt sich heraus, dass wenn 2 <= n <= k.

Hier bedeutet die Tatsache, dass der rekursive Aufruf k-mal erfolgt, dass es k Schichten in der Baumstruktur gibt, und es kann gesagt werden, dass 2 ^ k der Wert von n in der k Schicht ist. Wenn wir dies also für k mit n = 2 ^ k lösen, dann ist k = log (n), und wenn wir diese in die Gleichung von T (n) einsetzen, T (n) = nT (2 ^ k / 2 ^ k) + log (n) · n - log (n) - (1 + 2 + 4 + ・ ・ ・ ・ 2 + 2 ^ (log (n) -1) )) = nT(1) + nlog(n) - log(n) - (2^log(n) - 1) = nlog(n) - log(n) - (2^log(n) - 1)

Der erste Term ist von T (1) = 0 bis n * 0 = 0 und der letzte Term ist von der Summenformel (siehe Wikipedia). Da nlog (n)> 2 ^ log (n) ist, ist die Berechnungsreihenfolge O (nlog (n)). Übrigens sind bei der Zusammenführungssortierung sowohl der durchschnittliche Berechnungsbetrag als auch der beste Berechnungsbetrag mit dem schlechtesten Berechnungsbetrag identisch.

Grafik

Da die durchschnittliche Zeit tatsächlich berechnet und grafisch dargestellt wurde, werde ich den Quellcode und das Diagramm erstellen.

merge_sort.py

import math
import random
import time
import matplotlib.pyplot as plt

#Kopieren Sie hier die Zusammenführungssortierfunktion

sumOfTime = 0
sumPltList = []
nlognList = []
list1 = []
#Schleife, um Array-Längen 0-3000 zu machen
for i in range(3000):
    #Schleife zum 100-fachen Zusammenführen und Sortieren für jedes Array der Länge i
    for j in range(100):
        #0 für jeden Index~Geben Sie eine Zufallszahl von 100000 ein
        for k in range(i):
            list1.append(random.randint(0,100000))
        #Zeit vor dem Zusammenführen sortieren
        t0 = time.clock()
        merge(list1)
        #Zeit nach dem Zusammenführen sortieren
        t1 = time.clock()
        #Leeren Sie das Array für die nächste Zusammenführungssortierung
        list1 = []
        #Summe der Zeitunterschiede bei der Zusammenführungssortierung
        sumOfTime += t1 - t0
    #Durchschnittswert von 100 Zusammenführungssorten
    sumOfTime /= 100
    #Es gibt keine Basis, weil ich die durchschnittliche Zeit in der Liste speichere und 2000000 der Buchschwanz ist.
    sumPltList.append(sumOfTime*2000000)
    # log(0)Umgang mit ilog(i)Speichern Sie i in der Liste zum Vergleich
    if i != 0:
        nlognList.append(i*math.log(i)/math.log(2))
    else:
        nlognList.append(0.0)
    #Setzen Sie die Gesamtzeit alle 100 Male zurück
    sumOfTime = 0
#Sort und nlog zusammenführen(n)Zeichne eine Kurve
plt.plot(sumPltList, "r-", label = "Merge_Sort")
plt.plot(nlognList, "g-", label = "O(nlogn)")
#Etikett oben links anzeigen
plt.legend(loc=2)
#Bringen Sie Beschriftungen an der x- und y-Achse an
plt.xlabel('number of elements in a list')
plt.ylabel('time be taken')
#Grafik anzeigen
plt.show()

Das Multiplizieren von 2000000 mit der durchschnittlichen Zeit wird angepasst, indem die Ergebnisse bis zum Array mit der Länge 99 betrachtet werden. Die folgende Grafik zeigt jedoch, was mit den Ergebnissen bis zu einer Länge von 3000 passiert.

Da der Wert des Berechnungsbetrags von 100 bis 3000 Länge ebenfalls nahe am Wert von nlog (n) liegt, kann gesagt werden, dass das Berechnungsbetragsexperiment erfolgreich ist.

Dieses Mal habe ich den Zusammenführungssortierungsalgorithmus erklärt, implementiert und analysiert. Wenn Sie jedoch etwas falsch oder unklar finden, kommentieren Sie mich bitte oder senden Sie mir eine E-Mail. Vielen Dank. Nächstes Mal werde ich Python-Anweisungen oder andere Algorithmen in Python implementieren. Vielen Dank für das Lesen bis zum Ende!

Sortierlink zusammenführen: http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/merge-sort.html