Merge Sort ist einer der grundlegenden Algorithmen der Informatik, der bereits 1945 von dem großen Mathematiker John von Neumann formuliert wurde. Während seiner Teilnahme am Manhattan-Projekt stand Neumann vor der Notwendigkeit, riesige Datenmengen effizient zu verarbeiten. Die von ihm entwickelte Methode nutzte das Prinzip „Teile und herrsche“, was den Zeitaufwand für die Arbeit deutlich reduzierte.
Prinzip und Verwendung des Algorithmus
Die Merge-Sort-Methode wird bei Problemen mit dem Sortieren von Strukturen verwendet, die einen geordneten Zugriff auf Elemente haben, wie z. B. Arrays, Listen, Streams.
Während der Verarbeitung wird der anfängliche Datenblock in kleine Komponenten zerlegt, bis zu einem Element, das eigentlich schon eine sortierte Liste ist. Dann wird es in der richtigen Reihenfolge wieder zusammengesetzt.
Das Sortieren eines Arrays einer bestimmten Länge erfordert einen zusätzlichen Speicherbereich gleicher Größe, in dem das sortierte Array in Teilen gesammelt wird.
Die Methode kann verwendet werden, um jeden vergleichbaren Datentyp wie Zahlen oder Zeichenketten zu ordnen.
Sortiert zusammenführenGrundstücke
Um den Algorithmus zu verstehen, beginnen wir mit seiner Analyse am Ende - mit dem Mechanismus zum Zusammenführen sortierter Blöcke.
Stellen wir uns vor, wir hätten zwei beliebig sortierte Arrays von Zahlen, die miteinander kombiniert werden müssen, damit die Sortierung nicht unterbrochen wird. Der Einfachheit halber sortieren wir die Nummern in aufsteigender Reihenfolge.
Elementares Beispiel: Beide Arrays bestehen aus je einem Element.
int arr1={31}; int arr2={18};
Um sie zusammenzuführen, müssen Sie das Nullelement des ersten Arrays (vergessen Sie nicht, dass die Nummerierung bei Null beginnt) und das Nullelement des zweiten Arrays nehmen. Dies sind jeweils 31 und 18. Gemäß der Sortierbedingung sollte die Zahl 18 an erster Stelle stehen, da sie kleiner ist. Bringen Sie einfach die Zahlen in die richtige Reihenfolge:
int result={18, 31};
Sehen wir uns ein komplizierteres Beispiel an, bei dem jedes Array aus mehreren Elementen besteht:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Der Zusammenführungsalgorithmus besteht darin, kleinere Elemente nacheinander zu vergleichen und sie in der richtigen Reihenfolge in das resultierende Array einzufügen. Um die aktuellen Indizes im Auge zu beh alten, führen wir zwei Variablen ein - index1 und index2. Anfangs setzen wir sie auf Null, da die Arrays sortiert sind und die kleinsten Elemente am Anfang stehen.
int index1=0; int index2=0;
Schreiben wir Schritt für Schritt den gesamten Zusammenführungsprozess:
- Nimm das Element mit Index1 aus dem Array arr1 und das Element mit Index2 aus dem Array arr2.
- Vergleiche, wähle den kleinsten aus und trage ihn einresultierendes Array.
- Inkrementiere den aktuellen Index des kleineren Elements um 1.
- Fahren Sie mit dem ersten Schritt fort.
Auf der ersten Umlaufbahn sieht die Situation so aus:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; result[0]=arr1[0]; // Ergebnis=[2]
In der zweiten Runde:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; result[1]=arr2[0]; // Ergebnis=[2, 5]
Dritter:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; result[2]=arr2[1]; // Ergebnis=[2, 5, 6]
Und so weiter, bis das Ergebnis ein vollständig sortiertes Array ist: {2, 5, 6, 17, 21, 19, 30, 45}.
Gewisse Schwierigkeiten können auftreten, wenn Arrays mit unterschiedlichen Längen zusammengeführt werden. Was ist, wenn einer der aktuellen Indizes das letzte Element erreicht hat und im zweiten Array noch Mitglieder übrig sind?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 Schritt index1=0, index2=0; 1 2 Ergebnis={1, 2}; // 3 Schritte index1=1, index2=1; 4 < 5 Ergebnis={1, 2, 4}; //4 Schritte index1=2, index2=1 ??
Die Variable index1 hat den Wert 2 erreicht, aber das Array arr1 hat kein Element mit diesem Index. Hier ist alles einfach: Übertragen Sie einfach die verbleibenden Elemente des zweiten Arrays in das resultierende, wobei Sie ihre Reihenfolge beibeh alten.
Ergebnis={1, 2, 4, 5, 6, 7, 9};
Diese Situation zeigt uns die NotGleichen Sie den aktuellen Prüfindex mit der Länge des zusammenzuführenden Arrays ab.
Zusammenführungsschema für geordnete Sequenzen (A und B) unterschiedlicher Länge:
- Wenn die Länge beider Sequenzen größer als 0 ist, vergleiche A[0] und B[0] und verschiebe die kleinere in den Puffer.
- Wenn die Länge einer der Sequenzen 0 ist, nimm die restlichen Elemente der zweiten Sequenz und bewege sie, ohne ihre Reihenfolge zu ändern, zum Ende des Puffers.
Umsetzung der zweiten Stufe
Ein Beispiel für das Verbinden zweier sortierter Arrays in Java ist unten angegeben.
int a1=new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=neu int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int[a1.length + a2.length]; Ganzzahl i=0, j=0; for (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } sonst {int b=a2[j]; a3[k]=b; j++; } }
Hier:
- a1 und a2 sind die ursprünglichen sortierten Arrays, die zusammengeführt werden sollen;
- a3 – letzte Reihe;
- i und j sind Indizes aktueller Elemente für die Arrays a1 und a2.
Die erste und zweite if-Bedingung stellen sicher, dass die Indizes die Größe des Arrays nicht überschreiten. Der dritte bzw. vierte Bedingungsblock wird in das resultierende Array des kleineren Elements verschoben.
Teile und herrsche
Also, wir haben gelernt, das Sortierte zusammenzuführenSammlungen von Werten. Man kann sagen, dass der zweite Teil des Merge-Sortieralgorithmus – das Merge selbst – bereits sortiert wurde.
Sie müssen jedoch noch verstehen, wie Sie von der ursprünglichen unsortierten Zahlenreihe zu mehreren sortierten Zahlen gelangen, die zusammengeführt werden können.
Lassen Sie uns die erste Stufe des Algorithmus betrachten und lernen, wie man Arrays trennt.
Das ist nicht schwierig - die ursprüngliche Werteliste wird halbiert, dann wird jeder Teil auch gegabelt und so weiter, bis sehr kleine Blöcke erh alten werden.
Die Länge solcher minimalen Elemente kann gleich eins sein, dh sie können selbst ein sortiertes Array sein, aber das ist keine notwendige Bedingung. Die Größe des Blocks wird im Voraus bestimmt, und jeder geeignete Sortieralgorithmus, der effizient mit Arrays kleiner Größe arbeitet (z. B. Quicksort oder Insertion Sort), kann verwendet werden, um ihn zu ordnen.
So sieht es aus.
// ursprüngliches Array {34, 95, 10, 2, 102, 70}; // erste Teilung {34, 95, 10} und {2, 102, 70}; // zweiter Split {34} und {95, 10} und {2} und {102, 70}
Die resultierenden Blöcke, bestehend aus 1-2 Elementen, lassen sich sehr einfach anordnen.
Danach müssen Sie die bereits sortierten kleinen Arrays paarweise zusammenführen und dabei die Reihenfolge der Mitglieder beibeh alten, was wir bereits gelernt haben.
Umsetzung der ersten Stufe
Die rekursive Partitionierung eines Arrays ist unten dargestellt.
void mergeSort(T a, long start, long finish) { long split; Wenn(Start < Ziel) {Split=(Start + Ziel)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); merge(a, start, split, finish); } }
Was passiert in diesem Code:
-
Die Funktion mergeSort erhält das anfängliche Array
a
und die linken und rechten Grenzen der zu sortierenden Region (Indizes start und
- finish).
-
Wenn die Länge dieses Abschnitts größer als eins ist (
start < end
), dann wird er in zwei Teile geteilt (durch Index
- split), und jedes ist rekursiv sortiert.
-
Im rekursiven Funktionsaufruf für die linke Seite wird der Startindex des Plots und der Index
split
übergeben. Für den jeweils rechten ist der Anfang
- (split + 1) und das Ende der letzte Index des ursprünglichen Abschnitts.
-
Funktion
merge
ergibt zwei geordnete Sequenzen (
a[start]…a[split]
und
- a[split +1]…a[finish]) und fügt sie in sortierter Reihenfolge zusammen.
Die Mechanik der Merge-Funktion wurde oben besprochen.
Allgemeines Schema des Algorithmus
Die Methode zum Zusammenführen von Sortierreihen besteht aus zwei großen Schritten:
- Split das unsortierte Original-Array in kleine Stücke.
- Sammle sie paarweise und befolge die Sortierregel.
Eine große und komplexe Aufgabe wird in viele einfache Aufgaben zerlegt, die nacheinander gelöst werden und zum gewünschten Ergebnis führen.
Methodenbewertung
Die zeitliche Komplexität der Zusammenführungssortierung wird durch die Höhe des geteilten Baums bestimmtAlgorithmus und ist gleich der Anzahl der Elemente im Array (n) mal seinem Logarithmus (log n). Eine solche Schätzung nennt man logarithmisch.
Das ist sowohl Vor- als auch Nachteil der Methode. Seine Laufzeit ändert sich auch im schlimmsten Fall nicht, wenn das ursprüngliche Array in umgekehrter Reihenfolge sortiert wird. Bei der Verarbeitung komplett sortierter Daten bringt der Algorithmus jedoch keinen Zeitgewinn.
Es ist auch wichtig, die Speicherkosten der Merge-Sort-Methode zu beachten. Sie entsprechen der Größe der ursprünglichen Sammlung. In diesem zusätzlich zugewiesenen Bereich wird aus den Stücken ein sortiertes Array zusammengestellt.
Implementierung des Algorithmus
Die Pascal-Merge-Sortierung wird unten angezeigt.
Procedure MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: ganze Zahl; f1, f2: Text; b: boolesch Begincol:=0; Assign(f, name); zurücksetzen (f); Solange nicht EOF(f) beginnt read(f, a1); inkl. (Sp alte); Ende; schließen (f); Assign(f1, '{Name der 1. Hilfsdatei}'); Assign(f2, '{Name der 2. Hilfsdatei}'); s:=1; Während (s<kol) mit Reset(f) beginnen; umschreiben (f1); umschreiben (f2); Für i:=1 bis kol div 2 beginne Read(f, a1); Write(f1, a1, ' '); Ende; If (kol div 2) mod s0 then begin tmp:=kol div 2; Während tmp mod s0 mit Read(f, a1) beginnt; Write(f1, a1, ' '); inkl. (tmp); Ende; Ende; Solange nicht EOF(f) beginnt Read(f, a2); Write(f2, a2, ' '); Ende; schließen (f); schließen (f1); schließen (f2); umschreiben (f); zurücksetzen (f1); zurücksetzen (f2); Lesen (f1, a1); Lesen (f2, a2); Während (nicht EOF(f1)) und (nicht EOF(f2)) beginnen i:=0; j:=0; b:=wahr; While (b) and (not EOF(f1)) and (not EOF(f2)) do begin If (a1<a2) then beginWrite(f, a1, ' '); Lesen (f1, a1); inkl. (i); Ende sonst beginne Write(f, a2, ' '); Lesen (f2, a2); inkl. (j); Ende; Wenn (i=s) oder (j=s) dann b:=false; Ende; Wenn nicht b, dann begin While (i<s) und (nicht EOF(f1)) do begin Write(f, a1, ' '); Lesen (f1, a1); inkl. (i); Ende; Während (j<s) und (nicht EOF(f2)) Write(f, a2, ' ') beginnen; Lesen (f2, a2); inkl. (j); Ende; Ende; Ende; Solange nicht EOF(f1) beginnt tmp:=a1; Lesen (f1, a1); Wenn nicht EOF(f1), dann Write(f, tmp, ' ') else Write(f, tmp); Ende; Solange nicht EOF(f2) beginnt tmp:=a2; Lesen (f2, a2); Wenn nicht EOF(f2), dann Write(f, tmp, ' ') else Write(f, tmp); Ende; schließen (f); schließen (f1); schließen (f2); s:=s2; Ende; Löschen (f1); Löschen (f2); Ende;
Visuell sieht die Funktionsweise des Algorithmus so aus (oben - ungeordnete Sequenz, unten - geordnet).
Externe Datensortierung
Sehr oft ist es notwendig, einige Daten zu sortieren, die sich im externen Speicher des Computers befinden. In einigen Fällen haben sie eine beeindruckende Größe und können nicht im RAM platziert werden, um den Zugriff darauf zu erleichtern. Für solche Fälle werden externe Sortierverfahren eingesetzt.
Die Notwendigkeit, auf externe Medien zuzugreifen, verschlechtert die Effizienz der Verarbeitungszeit.
Die Komplexität der Arbeit besteht darin, dass der Algorithmus jeweils nur auf ein Element des Datenstroms zugreifen kann. Und in diesem Fall zeigt eines der besten Ergebnisse die Merge-Sort-Methode, die die Elemente zweier Dateien sequentiell nacheinander vergleichen kann.
Lese Daten vonexterne Quelle, ihre Verarbeitung und das Schreiben in die endgültige Datei werden in geordneten Blöcken (Serien) durchgeführt. Je nach Arbeitsweise mit der Größe geordneter Serien gibt es zwei Arten der Sortierung: einfaches und natürliches Zusammenführen.
Einfache Zusammenführung
Bei einer einfachen Zusammenführung ist die Serienlänge festgelegt.
In der unsortierten Originaldatei bestehen also alle Reihen aus einem Element. Nach dem ersten Schritt erhöht sich die Größe auf zwei. Weiter - 4, 8, 16 und so weiter.
So funktioniert es:
- Die Quelldatei (f) ist in zwei Hilfsdateien unterteilt - f1, f2.
- Sie werden wieder zu einer Datei zusammengeführt (f), aber gleichzeitig werden alle Elemente paarweise verglichen und bilden Paare. Die Seriengröße in diesem Schritt wird zwei.
- Schritt 1 wird wiederholt.
- Schritt 2 wird wiederholt, aber die bereits geordneten 2er werden zu sortierten 4er zusammengefügt.
- Die Schleife wird fortgesetzt und erhöht die Reihe bei jeder Iteration, bis die gesamte Datei sortiert ist.
Woher wissen Sie, dass die äußere Sortierung mit einer einfachen Zusammenführung abgeschlossen ist?
- neue Reihenlänge (nach Zusammenführung) nicht kleiner als die Gesamtzahl der Elemente;
- nur noch eine Folge übrig;
- Hilfsdatei f2 wurde leer gelassen.
Die Nachteile einer einfachen Zusammenführung sind: Da die Lauflänge bei jedem Zusammenführungsdurchgang festgelegt ist, dauert die Verarbeitung teilweise geordneter Daten genauso lange wie bei vollständig zufälligen Daten.
Natürliche Fusion
Diese Methode begrenzt die Länge nichtReihe, wählt aber das maximal Mögliche.
Sortieralgorithmus:
- Lesen der Anfangssequenz aus Datei f. Das erste empfangene Element wird in die Datei f1 geschrieben.
- Erfüllt der nächste Eintrag die Sortierbedingung, wird er dorthin geschrieben, wenn nicht, dann in die zweite Hilfsdatei f2.
- Auf diese Weise werden alle Datensätze der Quelldatei verteilt und in f1 eine geordnete Folge gebildet, die die aktuelle Größe der Serie bestimmt.
- Dateien f1 und f2 werden zusammengeführt.
- Der Zyklus wiederholt sich.
Aufgrund der nicht festgelegten Größe der Serie ist es notwendig, das Ende der Sequenz mit einem Sonderzeichen zu kennzeichnen. Daher erhöht sich beim Zusammenführen die Anzahl der Vergleiche. Außerdem kann die Größe einer der Hilfsdateien annähernd der Größe des Originals entsprechen.
Im Durchschnitt ist die natürliche Zusammenführung effizienter als die einfache Zusammenführung mit externer Sortierung.
Merkmale des Algorithmus
Beim Vergleich zweier identischer Werte behält die Methode ihre ursprüngliche Reihenfolge bei, ist also stabil.
Der Sortiervorgang kann sehr gut in mehrere Threads aufgeteilt werden.
Das Video demonstriert deutlich die Funktionsweise des Merge-Sort-Algorithmus.
