Menü

Sortierung in C ++ mit Beispielen zusammenführen

  • Haupt
  • Andere
  • Sortierung in C ++ mit Beispielen zusammenführen

merge sort c with examples

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

C ++ Merge Sort Technique.

Der Sortieralgorithmus zum Zusammenführen verwendet die Option „ teilen und erobern Strategie, bei der wir das Problem in Teilprobleme aufteilen und diese Teilprobleme individuell lösen.

Diese Teilprobleme werden dann kombiniert oder zu einer einheitlichen Lösung zusammengeführt.

=> Lesen Sie hier die beliebte C ++ - Schulungsserie.

Zusammenführen, sortieren

Was du lernen wirst:

beste kostenlose Screenshot-Software für Windows 10

Überblick

Die Zusammenführungssortierung wird mit den folgenden Schritten durchgeführt:

# 1) Die zu sortierende Liste wird durch Teilen der Liste im mittleren Element in zwei gleich lange Arrays unterteilt. Wenn die Anzahl der Elemente in der Liste entweder 0 oder 1 ist, wird die Liste als sortiert betrachtet.

#zwei) Jede Unterliste wird einzeln sortiert, indem die Zusammenführungssortierung rekursiv verwendet wird.

#3) Die sortierten Unterlisten werden dann kombiniert oder zu einer vollständigen sortierten Liste zusammengeführt.

Allgemeiner Algorithmus

Der allgemeine Pseudocode für die Zusammenführungssortiertechnik ist unten angegeben.

Deklarieren Sie ein Array Arr der Länge N.
Wenn N = 1 ist, ist Arr bereits sortiert
Wenn N> 1,
Links = 0, rechts = N-1
Finde Mitte = (links + rechts) / 2
Rufen Sie merge_sort (Arr, links, Mitte) auf => sortieren Sie die erste Hälfte rekursiv
Rufen Sie merge_sort (Arr, Mitte + 1, rechts) auf => sortieren Sie die zweite Hälfte rekursiv
Rufen Sie merge (Arr, left, middle, right) auf, um sortierte Arrays in den obigen Schritten zusammenzuführen.
Ausgang

Wie im obigen Pseudocode gezeigt, teilen wir beim Zusammenführungssortierungsalgorithmus das Array in zwei Hälften und sortieren jede Hälfte unter Verwendung der Zusammenführungssortierung rekursiv. Sobald die Unterarrays einzeln sortiert sind, werden die beiden Unterarrays zusammengeführt, um ein vollständig sortiertes Array zu bilden.

Pseudocode für Zusammenführungssortierung

Es folgt der Pseudocode für die Zusammenführungssortiertechnik. Erstens haben wir eine Prozedur-Merge-Sortierung, um das Array rekursiv in zwei Hälften zu teilen. Dann haben wir eine Zusammenführungsroutine, die die sortierten kleineren Arrays zusammenführt, um ein vollständig sortiertes Array zu erhalten.

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 end if end while while ( a has elements ) add a(0) to the end of c remove a(0) from a end while while ( b has elements ) add b(0) to the end of c remove b(0) from b end while return c end procedure

Lassen Sie uns nun die Zusammenführungssortiertechnik anhand eines Beispiels veranschaulichen.

Illustration

Sortierung zusammenführen Abbildung

Die obige Abbildung kann in tabellarischer Form dargestellt werden:

BestehenUnsortierte ListeTeilenSortierte Liste
ein{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
zwei{12,23,2,43}
{51,35,19,4}		{12.23} {2.43}
{51.35} {19.4}		{}
3{12.23} {2.43}
{51.35} {19.4}		{12.23} {2.43}
{35.51} {4.19}		{12.23} {2.43}
{35.51} {4.19}
4{12.23} {2.43}
{35.51} {4.19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
5{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
6{}{}{2,4,12,19,23,35,43,51}

Wie in der obigen Darstellung gezeigt, wird zuerst das Array in zwei Unterarrays der Länge 4 unterteilt. Jedes Unterarray wird weiter in zwei weitere Unterarrays der Länge 2 unterteilt. Jedes Unterarray wird dann weiter in ein Unterarray unterteilt von jeweils einem Element. Dieser gesamte Prozess ist der „Divide“ -Prozess.

Nachdem wir das Array in Unterarrays von jeweils einem Element unterteilt haben, müssen wir diese Arrays nun in sortierter Reihenfolge zusammenführen.

Wie in der obigen Abbildung gezeigt, betrachten wir jedes Subarray eines einzelnen Elements und kombinieren zuerst die Elemente, um Subarrays von zwei Elementen in sortierter Reihenfolge zu bilden. Als nächstes werden die sortierten Subarrays der Länge zwei sortiert und kombiniert, um zwei Subarrays der Länge vier zu bilden. Dann kombinieren wir diese beiden Unterarrays, um ein vollständig sortiertes Array zu bilden.

Iterative Zusammenführungssortierung

Der Algorithmus oder die Technik der Zusammenführungssortierung, die wir oben gesehen haben, verwendet die Rekursion. Es ist auch bekannt als “ rekursive Zusammenführungssortierung ”.

Wir wissen, dass rekursive Funktionen den Funktionsaufrufstapel verwenden, um den Zwischenzustand der aufrufenden Funktion zu speichern. Es speichert auch andere Buchhaltungsinformationen für Parameter usw. und verursacht Overhead in Bezug auf das Speichern des Aktivierungsdatensatzes zum Aufrufen der Funktion sowie das Fortsetzen der Ausführung.

All diese Gemeinkosten können beseitigt werden, wenn iterative Funktionen anstelle von rekursiven verwendet werden. Der obige Zusammenführungssortieralgorithmus kann auch leicht in iterative Schritte unter Verwendung von Schleifen und Entscheidungsfindung umgewandelt werden.

Wie die rekursive Zusammenführungssortierung weist auch die iterative Zusammenführungssortierung eine O (nlogn) -Komplexität auf, weshalb sie in Bezug auf die Leistung gleichwertig sind. Wir sind einfach in der Lage, die Gemeinkosten zu senken.

In diesem Tutorial haben wir uns auf die rekursive Zusammenführungssortierung konzentriert. Als Nächstes implementieren wir die rekursive Zusammenführungssortierung in C ++ und Java.

Im Folgenden wird eine Implementierung der Zusammenführungssortiertechnik unter Verwendung von C ++ angegeben.

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

Ausgabe:

Geben Sie die Anzahl der zu sortierenden Elemente ein: 10

Geben Sie 10 zu sortierende Elemente ein: 101 10 2 43 12 54 34 64 89 76

Sortiertes Array

2 10 12 34 43 54 64 76 89 101

In diesem Programm haben wir zwei Funktionen definiert: Zusammenführen, sortieren und gehen . In der Funktion merge_sort teilen wir das Array in zwei gleiche Arrays auf und rufen die Merge-Funktion für jedes dieser Sub-Arrays auf. In der Zusammenführungsfunktion führen wir die eigentliche Sortierung für diese Unterarrays durch und führen sie dann zu einem vollständig sortierten Array zusammen.

Als Nächstes implementieren wir die Merge Sort-Technik in der Java-Sprache.

class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i

Ausgabe:

Eingabearray

101 10 2 43 12 54 34 64 89 76

Array sortiert mit Merge Sort

2 10 12 34 43 54 64 76 89 101

Auch in der Java-Implementierung verwenden wir dieselbe Logik wie in der C ++ - Implementierung.

Die Zusammenführungssortierung ist eine effiziente Methode zum Sortieren von Listen und wird hauptsächlich zum Sortieren verknüpfter Listen verwendet. Da ein Divide-and-Conquer-Ansatz verwendet wird, ist die Merge-Sort-Technik für kleinere und größere Arrays gleichermaßen effizient.

Komplexitätsanalyse des Merge-Sort-Algorithmus

Wir wissen, dass wir das Array zunächst in zwei gleiche Hälften teilen, um die Sortierung mithilfe der Zusammenführungssortierung durchzuführen. Dies wird durch 'log n' dargestellt, eine logarithmische Funktion, und die Anzahl der durchgeführten Schritte beträgt höchstens log (n + 1).

Als nächstes benötigen wir einen einzelnen Schritt, d. H. O (1), um das mittlere Element des Arrays zu finden.

Um dann die Unterarrays zu einem Array von n Elementen zusammenzuführen, benötigen wir eine Laufzeit von O (n).

Somit beträgt die Gesamtzeit für die Zusammenführungssortierung n (log n + 1), was uns die zeitliche Komplexität von O (n * logn) gibt.

Zeitkomplexität im schlimmsten FallO (n * log n)
Best-Case-ZeitkomplexitätO (n * log n)
Durchschnittliche ZeitkomplexitätO (n * log n)
RaumkomplexitätAuf)

Die zeitliche Komplexität für die Zusammenführungssortierung ist in allen drei Fällen (schlechteste, beste und durchschnittliche) gleich, da das Array immer in Unterarrays unterteilt wird und die Unterarrays dann linear linear zusammengeführt werden.

Die Zusammenführungssortierung nimmt immer den gleichen Speicherplatz ein wie unsortierte Arrays. Wenn es sich bei der zu sortierenden Liste um ein Array handelt, sollte die Zusammenführungssortierung daher nicht für sehr große Arrays verwendet werden. Die Zusammenführungssortierung kann jedoch effektiver für die Sortierung verknüpfter Listen verwendet werden.

Fazit

Die Sortierung zusammenführen verwendet die Strategie „Teilen und Erobern“, bei der das Array oder die Liste in zahlreiche Unterarrays unterteilt und einzeln sortiert und dann zu einem vollständig sortierten Array zusammengeführt wird.

Die Zusammenführungssortierung ist schneller als andere Sortiermethoden und funktioniert auch für kleinere und größere Arrays effizient.

Wir werden mehr über Quick Sort in unserem kommenden Tutorial erfahren!

=> Sehen Sie sich hier den C ++ - Schulungsleitfaden für Anfänger an.

Literatur-Empfehlungen

^