Sortieralgorithmus zusammenführen

In diesem Tutorial erfahren Sie mehr über das Sortieren von Zusammenführungen. Außerdem finden Sie Arbeitsbeispiele für die Zusammenführungssortierung C, C ++, Java und Python.

Merge Sort ist einer der beliebtesten Sortieralgorithmen, der auf dem Prinzip des Divide and Conquer-Algorithmus basiert.

Hier ist ein Problem in mehrere Unterprobleme unterteilt. Jedes Unterproblem wird einzeln gelöst. Schließlich werden Teilprobleme kombiniert, um die endgültige Lösung zu bilden.

Beispiel für Sortieren zusammenführen

Strategie teilen und erobern

Mit der Divide and Conquer- Technik teilen wir ein Problem in Teilprobleme. Wenn die Lösung für jedes Teilproblem fertig ist, kombinieren wir die Ergebnisse der Teilprobleme, um das Hauptproblem zu lösen.

Angenommen, wir müssten ein Array A sortieren. Ein Unterproblem wäre, einen Unterabschnitt dieses Arrays zu sortieren, der am Index p beginnt und am Index r endet, der als A (p… r) bezeichnet wird.

Teilen
Wenn q der halbe Punkt zwischen p und r ist, können wir das Subarray A (p… r) in zwei Arrays A (p… q) und A (q + 1, r) aufteilen.

Erobern
Im Eroberungsschritt versuchen wir, sowohl die Subarrays A (p… q) als auch A (q + 1, r) zu sortieren. Wenn wir den Basisfall noch nicht erreicht haben, teilen wir diese beiden Subarrays erneut und versuchen, sie zu sortieren.

Kombinieren
Wenn der Eroberungsschritt den Basisschritt erreicht und wir zwei sortierte Subarrays A (p… q) und A (q + 1, r) für Array A (p… r) erhalten, kombinieren wir die Ergebnisse, indem wir ein sortiertes Array A ( p… r) aus zwei sortierten Subarrays A (p… q) und A (q + 1, r).

Der MergeSort-Algorithmus

Die MergeSort-Funktion teilt das Array wiederholt in zwei Hälften, bis wir ein Stadium erreichen, in dem wir versuchen, MergeSort auf einem Subarray der Größe 1 durchzuführen, dh p == r.

Danach kommt die Zusammenführungsfunktion ins Spiel und kombiniert die sortierten Arrays zu größeren Arrays, bis das gesamte Array zusammengeführt ist.

 MergeSort (A, p, r): Wenn p> r ist, geben Sie q = (p + r) / 2 zurück. MergeSort (A, p, q) mergeSort (A, q + 1, r) merge (A, p, q, r) )

Um ein ganzes Array zu sortieren, müssen wir aufrufen MergeSort(A, 0, length(A)-1).

Wie in der Abbildung unten gezeigt, teilt der Zusammenführungssortierungsalgorithmus das Array rekursiv in Hälften, bis wir den Basisfall des Arrays mit 1 Element erreichen. Danach nimmt die Zusammenführungsfunktion die sortierten Unterarrays auf und führt sie zusammen, um das gesamte Array schrittweise zu sortieren.

Sortierung in Aktion zusammenführen

Der Zusammenführungsschritt der Zusammenführungssortierung

Jeder rekursive Algorithmus ist abhängig von einem Basisfall und der Fähigkeit, die Ergebnisse aus Basisfällen zu kombinieren. Die Zusammenführungssortierung ist nicht anders. Der wichtigste Teil des Algorithmus zum Sortieren von Zusammenführungen ist, wie Sie es erraten haben, der Zusammenführungsschritt.

Der Zusammenführungsschritt ist die Lösung für das einfache Problem, zwei sortierte Listen (Arrays) zusammenzuführen, um eine große sortierte Liste (Array) zu erstellen.

Der Algorithmus verwaltet drei Zeiger, einen für jedes der beiden Arrays und einen zum Verwalten des aktuellen Index des endgültig sortierten Arrays.

Haben wir das Ende eines der Arrays erreicht? Nein: Aktuelle Elemente beider Arrays vergleichen Kleines Element in sortiertes Array kopieren Zeiger des Elements mit kleinerem Element verschieben Ja: Alle verbleibenden Elemente eines nicht leeren Arrays kopieren
Schritt zusammenführen

Schreiben des Codes für den Zusammenführungsalgorithmus

Ein bemerkenswerter Unterschied zwischen dem oben beschriebenen Zusammenführungsschritt und dem für die Zusammenführungssortierung verwendeten besteht darin, dass wir die Zusammenführungsfunktion nur für aufeinanderfolgende Unterarrays ausführen.

Aus diesem Grund benötigen wir nur das Array, die erste Position, den letzten Index des ersten Subarrays (wir können den ersten Index des zweiten Subarrays berechnen) und den letzten Index des zweiten Subarrays.

Unsere Aufgabe ist es, zwei Subarrays A (p… q) und A (q + 1… r) zusammenzuführen, um ein sortiertes Array A (p… r) zu erstellen. Die Eingänge für die Funktion sind also A, p, q und r

Die Zusammenführungsfunktion funktioniert wie folgt:

  1. Erstellen Sie Kopien der Subarrays L ← A(p… q)und M ← A (q + 1… r).
  2. Erstellen Sie drei Zeiger i, j und k
    1. Ich behalte den aktuellen Index von L bei, beginnend bei 1
    2. j behält den aktuellen Index von M bei, beginnend bei 1
    3. k behält den aktuellen Index von A (p… q) bei, beginnend bei p.
  3. Bis wir das Ende von L oder M erreichen, wählen Sie das größere der Elemente aus L und M aus und platzieren Sie sie an der richtigen Position bei A (p… q).
  4. Wenn uns die Elemente in L oder M ausgehen, nehmen Sie die verbleibenden Elemente auf und geben Sie A ein (p… q).

Im Code würde dies so aussehen:

 // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )

Die Funktion Merge () wird Schritt für Schritt erklärt

In dieser Funktion passiert viel. Nehmen wir also ein Beispiel, um zu sehen, wie dies funktionieren würde.

Wie immer sagt ein Bild tausend Worte.

Zusammenführen von zwei aufeinanderfolgenden Array-Subarrays

Das Array A (0… 5) enthält zwei sortierte Subarrays A (0… 3) und A (4… 5). Lassen Sie uns sehen, wie die Zusammenführungsfunktion die beiden Arrays zusammenführt.

 void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)

Schritt 1: Erstellen Sie doppelte Kopien der zu sortierenden Sub-Arrays

  // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9)
Erstellen Sie Kopien von Subarrays zum Zusammenführen

Schritt 2: Pflegen Sie den aktuellen Index der Sub-Arrays und des Haupt-Arrays

  int i, j, k; i = 0; j = 0; k = p;
Pflegen Sie Indizes von Kopien des Unterarrays und des Hauptarrays

Schritt 3: Bis wir das Ende von L oder M erreichen, wählen Sie zwischen den Elementen L und M eine größere Auswahl und platzieren Sie sie an der richtigen Position bei A (p… r).

  while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; )
Vergleich einzelner Elemente sortierter Subarrays bis zum Ende eines

Schritt 4: Wenn uns die Elemente in L oder M ausgehen, nehmen Sie die verbleibenden Elemente auf und geben Sie A ein (p… r).

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Kopieren Sie die verbleibenden Elemente aus dem ersten Array in das Haupt-Subarray 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopieren Sie die verbleibenden Elemente des zweiten Arrays in das Haupt-Subarray

Dieser Schritt wäre erforderlich gewesen, wenn die Größe von M größer als L gewesen wäre.

Am Ende der Zusammenführungsfunktion wird das Subarray A (p… r) sortiert.

Beispiele für Python, Java und C / C ++

Python Java C C ++ 
 # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array) 
 // Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
 // Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
 // Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )

Sortierkomplexität zusammenführen

Zeitliche Komplexität

Best-Case-Komplexität: O (n * log n)

Worst-Case-Komplexität: O (n * log n)

Durchschnittliche Fallkomplexität: O (n * log n)

Raumkomplexität

Die Raumkomplexität der Zusammenführungssortierung ist O (n).

Sortieranwendungen zusammenführen

  • Inversionszählungsproblem
  • Externe Sortierung
  • E-Commerce-Anwendungen

Interessante Beiträge...