Eine Einführung in den Merge-Sortierungsalgorithmus

Merge-Sort ist ein Sortieralgorithmus, der auf der "Divide and Conquer"-Technik basiert. Es ist einer der effizientesten Sortieralgorithmen.

In diesem Artikel erfahren Sie mehr über die Funktionsweise des Merge-Sort-Algorithmus, den Algorithmus des Merge-Sorts, seine Zeit- und Raumkomplexität und ihre Implementierung in verschiedenen Programmiersprachen wie C++, Python und, JavaScript.

Wie funktioniert der Merge-Sort-Algorithmus?

Merge-Sort funktioniert nach dem Prinzip des Teilens und Herrschens. Merge-Sort zerlegt ein Array wiederholt in zwei gleiche Unterarrays, bis jedes Unterarray aus einem einzigen Element besteht. Schließlich werden alle diese Unterarrays so zusammengeführt, dass das resultierende Array sortiert wird.

Dieses Konzept lässt sich anhand eines Beispiels effizienter erklären. Betrachten Sie ein unsortiertes Array mit den folgenden Elementen: {16, 12, 15, 13, 19, 17, 11, 18}.

Hier teilt der Merge-Sort-Algorithmus das Array in zwei Hälften, ruft sich selbst für die beiden Hälften auf und führt dann die beiden sortierten Hälften zusammen.

Sortieralgorithmus zusammenführen

Unten ist der Algorithmus der Zusammenführungssortierung:

MergeSort (arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
Rückkehr
sonst
Finden Sie den mittleren Index, der das Array in zwei Hälften teilt: 
MiddleIndex = leftIndex + (rightIndex-leftIndex)/2
Rufen Sie mergeSort() für die erste Hälfte auf: 
MergeSort aufrufen (arr, leftIndex, middleIndex)
Rufen Sie mergeSort() für die zweite Hälfte auf:
MergeSort aufrufen (arr, middleIndex+1, rightIndex)
Füge die beiden in Schritt 2 und 3 sortierten Hälften zusammen:
Anrufzusammenführung (arr, leftIndex, middleIndex, rightIndex)

Verbunden: Was ist Rekursion und wie wird sie verwendet?

Zeit- und Raumkomplexität des Merge-Sort-Algorithmus

Der Sortieralgorithmus Merge kann in Form der folgenden Wiederholungsbeziehung ausgedrückt werden:

T(n) = 2T(n/2) + O(n)

Nachdem Sie diese Rekursionsbeziehung mit dem Master-Theorem oder der Rekursionsbaummethode gelöst haben, erhalten Sie die Lösung als O(n logn). Somit ist die Zeitkomplexität des Merge-Sort-Algorithmus O(n anmelden).

Die Zeitkomplexität der Zusammenführungssortierung im günstigsten Fall: O(n anmelden)

Die durchschnittliche Zeitkomplexität der Zusammenführungssortierung: O(n anmelden)

Die Worst-Case-Zeitkomplexität der Merge-Sortierung: O(n anmelden)

Verbunden: Was ist Big-O-Notation?

Die Hilfsraumkomplexität des Merge-Sort-Algorithmus ist Auf) wie nein Bei der Merge-Sort-Implementierung wird zusätzlicher Speicherplatz benötigt.

C++-Implementierung des Merge-Sort-Algorithmus

Unten ist die C++-Implementierung des Merge-Sort-Algorithmus:

// C++-Implementierung des
// Sortieralgorithmus zusammenführen
#einschließen 
Verwenden des Namensraums std;
// Diese Funktion führt zwei Subarrays von arr[] zusammen
// Linkes Unterarray: arr[leftIndex..middleIndex]
// Rechtes Subarray: arr[middleIndex+1..rightIndex]
void merge (int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = MiddleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - MiddleIndex;
// Temporäre Arrays erstellen
int L[leftSubarraySize], R[rightSubarraySize];
// Daten in temporäre Arrays L[] und R[] kopieren
für (int i = 0; i < leftSubarraySize; ich++)
L[i] = arr[linker Index + i];
für (intj = 0; j < rightSubarraySize; j++)
R[j] = arr[mittlerer Index + 1 + j];
// Die temporären Arrays wieder in arr[leftIndex..rightIndex] zusammenführen
// Anfangsindex des linken Unterarrays
int i = 0;
// Anfangsindex des rechten Unterarrays
intj = 0;
// Anfangsindex des zusammengeführten Subarrays
int k = linker Index;
while (i < leftSubarraySize && j < rightSubarraySize)
{
wenn (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
sonst
{
arr[k] = R[j];
j++;
}
k++;
}
// Wenn noch einige Elemente in L[] vorhanden sind
// Nach arr[] kopieren
while (i < leftSubarraySize)
{
arr[k] = L[i];
i++;
k++;
}
// Wenn noch einige Elemente in R[] vorhanden sind
// Nach arr[] kopieren
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort (int arr[], int leftIndex, int rightIndex)
{
if (leftIndex >= rightIndex)
{
Rückkehr;
}
int MiddleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, mittlererIndex+1, rechterIndex);
Zusammenführen (arr, leftIndex, middleIndex, rightIndex);
}
// Funktion zum Drucken der Elemente
// des Arrays
void printArray (int arr[], int Größe)
{
für (int i = 0; ich < Größe; ich++)
{
cout << arr[i] << " ";
}
cout << endl;
}
// Fahrercode
int main()
{
int arr[] = {16, 12, 15, 13, 19, 17, 11, 18};
int size = sizeof (arr) / sizeof (arr[0]);
cout << "Unsortiertes Array:" << endl;
printArray (arr, Größe);
mergeSort (arr, 0, Größe - 1);
cout << "Sortiertes Array:" << endl;
printArray (arr, Größe);
0 zurückgeben;
}

Ausgabe:

Unsortiertes Array:
16 12 15 13 19 17 11 18 
Sortiertes Array:
11 12 13 15 16 17 18 19

JavaScript-Implementierung des Merge-Sort-Algorithmus

Unten sehen Sie die JavaScript-Implementierung des Merge-Sort-Algorithmus:

// JavaScript-Implementierung des
// Sortieralgorithmus zusammenführen
// Diese Funktion führt zwei Subarrays von arr[] zusammen
// Linkes Unterarray: arr[leftIndex..middleIndex]
// Rechtes Subarray: arr[middleIndex+1..rightIndex]
Funktion merge (arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - MiddleIndex;
// Temporäre Arrays erstellen
var L = neues Array (leftSubarraySize);
var R = neues Array (rightSubarraySize);
// Daten in temporäre Arrays L[] und R[] kopieren
für (lassen Sie i = 0; ichL[i] = arr[linker Index + i];
}
für (es sei j = 0; jR[j] = arr[mittlerer Index + 1 + j];
}
// Die temporären Arrays wieder in arr[leftIndex..rightIndex] zusammenführen
// Anfangsindex des linken Unterarrays
vari = 0;
// Anfangsindex des rechten Unterarrays
varj = 0;
// Anfangsindex des zusammengeführten Subarrays
var k = linker Index;
while (i < leftSubarraySize && j < rightSubarraySize)
{
wenn (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
sonst
{
arr[k] = R[j];
j++;
}
k++;
}
// Wenn noch einige Elemente in L[] vorhanden sind
// Nach arr[] kopieren
while (i < leftSubarraySize)
{
arr[k] = L[i];
i++;
k++;
}
// Wenn noch einige Elemente in R[] vorhanden sind
// Nach arr[] kopieren
while (j < rightSubarraySize)
{
arr[k] = R[j];
j++;
k++;
}
}
Funktion mergeSort (arr, leftIndex, rightIndex) {
if (leftIndex >= rightIndex) {
Rückkehr
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, mittlererIndex+1, rechterIndex);
Zusammenführen (arr, leftIndex, middleIndex, rightIndex);
}
// Funktion zum Drucken der Elemente
// des Arrays
Funktion printArray (arr, Größe) {
für (lassen Sie i = 0; ichdocument.write (arr[i] + " ");
}
document.write("
");
}
// Treibercode:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
Var-Größe = Arr.Länge;
document.write("Unsortiertes Array:
");
printArray (arr, Größe);
mergeSort (arr, 0, Größe - 1);
document.write("Sortiertes Array:
");
printArray (arr, Größe);

Ausgabe:

Unsortiertes Array:
16 12 15 13 19 17 11 18
Sortiertes Array:
11 12 13 15 16 17 18 19

Verbunden: Dynamische Programmierung: Beispiele, häufige Probleme und Lösungen

Python-Implementierung des Merge-Sort-Algorithmus

Unten ist die Python-Implementierung des Merge-Sort-Algorithmus:

# Python-Implementierung des
# Sortieralgorithmus zusammenführen
def mergeSort (arr):
wenn len (arr) > 1:
# Den mittleren Index des Arrays finden
midIndex = len (arr)//2
# Linke Hälfte des Arrays
L = arr[:middleIndex]
# Rechte Hälfte des Arrays
R = arr[middleIndex:]
# Sortieren der ersten Hälfte des Arrays
zusammenführenSortieren (L)
# Sortieren der zweiten Hälfte des Arrays
ZusammenführenSortieren (R)
# Anfangsindex des linken Unterarrays
ich = 0
# Anfangsindex des rechten Subarrays
j = 0
# Anfangsindex des zusammengeführten Subarrays
k = 0
# Daten in die temporären Arrays L[] und R[] kopieren
während i < len (L) und j < len (R):
wenn L[i] < R[j]:
arr[k] = L[i]
ich = ich + 1
sonst:
arr[k] = R[j]
j = j + 1
k = k + 1
# Überprüfen, ob noch einige Elemente vorhanden sind
während ich < len (L):
arr[k] = L[i]
ich = ich + 1
k = k + 1
während j < len (R):
arr[k] = R[j]
j = j + 1
k = k + 1
# Funktion zum Drucken der Elemente
# des Arrays
def printArray (arr, Größe):
für i im Bereich (Größe):
print (arr[i], end="")
drucken()
# Fahrercode
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
Größe = len (arr)
print("Unsortiertes Array:")
printArray (arr, Größe)
zusammenführenSortieren (arr)
print("Sortiertes Array:")
printArray (arr, Größe)

Ausgabe:

Unsortiertes Array:
16 12 15 13 19 17 11 18
Sortiertes Array:
11 12 13 15 16 17 18 19

Andere Sortieralgorithmen verstehen

Sortieren ist einer der am häufigsten verwendeten Algorithmen in der Programmierung. Sie können Elemente in verschiedenen Programmiersprachen mit verschiedenen Sortieralgorithmen wie Quick-Sort, Bubble-Sort, Merge-Sort, Insert-Sort usw. sortieren.

Bubble-Sort ist die beste Wahl, wenn Sie den einfachsten Sortieralgorithmus kennenlernen möchten.

Eine Einführung in den Bubble-Sort-Algorithmus

Der Bubble-Sort-Algorithmus: eine ausgezeichnete Einführung in das Sortieren von Arrays.

Weiter lesen

Über den Autor