Zusammenführen Sortieren

1. Zusammenführen Sortieren
2. Zusammenführen Sortieren Beispiel
3. Implementierung des Merge-Sortieralgorithmus
4. Komplexität des Merge-Sortieralgorithmus

Merge Sort ist einer der beliebtesten und effizientesten Sortieralgorithmen. Er basiert auf dem Prinzip des Divide-and-Conquer-Algorithmus. Er funktioniert, indem das Array wiederholt in zwei Hälften geteilt wird, bis wir das Array in einzelne Elemente aufgeteilt bekommen. Ein einzelnes Element ist ein sortiertes Array in sich selbst. Merge Sort führt diese kleinen sortierten Arrays wiederholt zusammen, um größere sortierte Unterarrays zu erzeugen, bis wir ein endgültiges sortiertes Array erhalten. Es wird häufig in E-Commerce-Anwendungen verwendet.

Zusammenführen Sortieren

Der Top-Down-Merge-Sort-Ansatz beginnt oben mit dem gesamten Array und arbeitet sich mit Rekursion nach unten zu den einzelnen Elementen vor.

Angenommen, wir haben ein unsortiertes Array A[] mit n Elementen.

MergeSort()

Merge()

Zusammenführen Sortieren Beispiel

Angenommen, wir haben das Array: (5,3,4,2,1,6). Wir werden es mit dem Merge-Sort-Algorithmus sortieren.

Wir erhalten das sortierte Array - (1 2 3 4 5 6)

Implementierung des Merge-Sortieralgorithmus

#include <iostream>
using namespace std;

void merge(int arr[], int beg, int mid, int end) {
  int output[end - beg + 1];
  int i = beg, j = mid + 1, k = 0;
  // add smaller of both elements to the output
  while (i <= mid && j <= end) {
    if (arr[i] <= arr[j]) {
      output[k] = arr[i];
      k += 1;
      i += 1;
    } else {
      output[k] = arr[j];
      k += 1;
      j += 1;
    }
  }
  // remaining elements from first array
  while (i <= mid) {
    output[k] = arr[i];
    k += 1;
    i += 1;
  }
  // remaining elements from the second array
  while (j <= end) {
    output[k] = arr[j];
    k += 1;
    j += 1;
  }
  // copy output to the original array
  for (i = beg; i <= end; i += 1) {
    arr[i] = output[i - beg];
  }
}

void mergeSort(int arr[], int beg, int end) {
  if (beg < end) {
    int mid = (beg + end) / 2;
    // divide and conquer
    mergeSort(arr, beg, mid);      // divide : first half
    mergeSort(arr, mid + 1, end);  // divide: second half
    merge(arr, beg, mid, end);     // conquer
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  mergeSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Komplexität des Merge-Sortieralgorithmus

Zeitkomplexität

• Durchschnittlicher Fall

Merge Sort ist ein rekursiver Algorithmus. Die folgende Rekursionsrelation gibt den Zeitkomplexitätsausdruck für Merge-Sort an.

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

Das Ergebnis dieser Rekursionsrelation ist T(n) = nLogn. Wir können es auch so sehen, dass ein Array der Größe n in maximal Logn Teile unterteilt wird und das Zusammenführen jedes Teils O(n) Zeit benötigt.

Daher ist die Zeitkomplexität in der Größenordnung von [Big Theta]: O(nLogn).

• Schlimmster Fall

Die Zeitkomplexität im schlimmsten Fall ist [Big O]: O(nLogn).

• Bester Fall

Die Zeitkomplexität im besten Fall ist [Big Omega]: O(nLogn). Sie ist identisch mit der Zeitkomplexität im schlimmsten Fall.

Raumkomplexität

Die Platzkomplexität für den Merge-Sort-Algorithmus ist O(n), da n Hilfsplatz für die Speicherung des sortierten Subarrays im Hilfsarray benötigt wird.