Sortieralgorithmus zusammenführen

алгоритм, сортировка слиянием, Merge Sort Algorithm, сортировка

Merge Sort ist eine Art Teile-und-Herrsche-Algorithmus in der Computerprogrammierung. Es ist einer der beliebtesten Sortieralgorithmen und eine großartige Möglichkeit, Vertrauen in die Erstellung rekursiver Algorithmen aufzubauen.

Teile-und-herrsche-Strategie

Mit der Divide-and-Conquer-Technik teilen wir das Problem in Teilaufgaben auf. Wenn die Lösung für jedes Teilproblem fertig ist, „kombinieren“ wir die Ergebnisse aus den Teilproblemen, um das Hauptproblem zu lösen.

Angenommen, wir müssten ein Array A sortieren. Die Teilaufgabe wäre, einen Unterabschnitt dieses Arrays zu sortieren, beginnend beim Index p und endend beim Index r, bezeichnet als A[p..r].

Teilen

Wenn q ein Zwischenpunkt zwischen p und r ist, dann können wir das Subarray A[p..r] in zwei Arrays A[p..q] und A[q + 1, r] aufteilen.

Besitze es

Im Eroberungsschritt versuchen wir, die beiden Subarrays A[p..q] und A[q + 1, r] zu sortieren. Wenn wir den Basisfall noch nicht erreicht haben, trennen wir diese beiden Subarrays wieder und versuchen sie zu sortieren.

Kombinieren

Wenn der Erobererschritt den Basisschritt erreicht und wir zwei sortierte Subarrays A[p..q] und A[q + 1, r] für das Array A[p..r] erhalten, kombinieren wir die Ergebnisse und erstellen ein sortiertes Array A [p..r] zweier sortierter Subarrays A[p..q] und A[q + 1, r]

Sortieralgorithmus zusammenführen

Die MergeSort-Funktion teilt das Array wiederholt in zwei Hälften, bis wir eine Phase erreichen, in der wir versuchen, MergeSort auf einem Subarray der Größe 1 durchzuführen, d.h. p == r.
Danach kommt die Merge-Funktion ins Spiel, die die sortierten Arrays zu größeren Arrays zusammenführt, bis das gesamte Array zusammengeführt ist.

MergeSort(A, p, r)
    If p > r 
        return;
    q = (p+r)/2;
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

Um das gesamte Array zu sortieren, müssen wir MergeSort(A, 0, length(A)-1) aufrufen.
Wie in der Abbildung unten gezeigt, teilt der Merge-Sort-Algorithmus das Array rekursiv in zwei Hälften, bis wir den Basisfall eines Arrays mit 1 Element erreichen. Die Zusammenführungsfunktion wählt dann die sortierten Unterarrays aus und führt sie zusammen, um das gesamte Array nach und nach zu sortieren.

Merge-Sortierung-Merge-Schritt

Jeder rekursive Algorithmus hängt von einem Basisfall und der Fähigkeit ab, Ergebnisse aus Basisfällen zu kombinieren. Zusammenführungssortierung ist keine Ausnahme. Der wichtigste Teil des Algorithmus ist der "Merge"-Schritt.

Der Zusammenführungsschritt ist eine Lösung für das einfache Problem, zwei sortierte Listen (Arrays) zu kombinieren, 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ültigen sortierten Arrays.

Достигли ли мы конца какого-либо из массивов?
    Нет:
        Сравните текущие элементы обоих массивов
        Скопируйте меньший элемент в отсортированный массив
        Переместить указатель на элемент, содержащий меньший элемент
    Да:
        Скопировать все оставшиеся элементы непустого массива

Da im zweiten Array keine Elemente mehr vorhanden sind und wir wissen, dass beide Arrays beim Start sortiert wurden, können wir die restlichen Elemente direkt aus dem ersten Array kopieren

Code für den Merge-Algorithmus schreiben

Ein bemerkenswerter Unterschied zwischen dem oben beschriebenen Zusammenführungsschritt und dem, den wir für die Zusammenführungssortierung verwenden, besteht darin, dass die Zusammenführungsfunktion nur für aufeinanderfolgende Unterarrays ausgeführt wird.

Deshalb brauchen 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] zu einem sortierten Array A[p..r] zu kombinieren. Somit sind die Eingabedaten für die Funktion A, p, q und r

Die Merge-Funktion funktioniert so:

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
3. i behält den aktuellen Index L bei, beginnend bei 1
4. j behält den aktuellen Index von M bei, beginnend bei 1
5. k behält den aktuellen Index von A [p..q] bei, beginnend mit p
6. Bis wir das Ende von L oder M erreicht haben, wähle das größere der Elemente aus L und M und platziere sie an der richtigen Stelle in A[p..q]
7. Wenn uns die Elemente in L oder M ausgehen, nehmen Sie die restlichen Elemente und geben Sie A [p..q] ein

Im Code sieht das so aus:

void merge(int A[], int p, int q, int r)
{
    /* Создание L ← A[p..q] и M ← A[q+1..r] */
    int n1 = q - p + 1;
    int n2 =  r - q;

    int L[n1], M[n2];

    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (j = 0; j < n2; j++)
        M[j] = A[q + 1 + j];

    /* Поддержание текущего индекса вложенных массивов и основного массива */
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 


    /* Пока мы не достигнем конца L или M, выбираем большее из элементов L и M и помещаем их в правильное положение в точке 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++;
    }

    /* Когда у нас кончаются элементы в L или M, возьмите оставшиеся элементы и поместите в A [p..r]*/
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}

Funktion Schritt für Schritt zusammenführen

In dieser Funktion gibt es viel zu tun, also schauen wir uns ein Beispiel an, um zu sehen, wie es funktionieren würde.

Das Array A[0..8] enthält zwei sortierte Subarrays A[1..5] und A[6..7]. Mal sehen, wie die Zusammenführungsfunktion zwei Arrays zusammenführt.

void merge(int A[], int p = 1, int q = 4, int 6)
{

Schritt 1. Erstellen Sie doppelte Kopien von Subarrays zum Sortieren

 /* Создание L ← A[p..q] и M ← A[q+1..r] */
    n1 = 4 - 1 + 1 = 4;
    n2 =  6 - 4 = 2;

    int L[4], M[2];

    for (i = 0; i < 4; i++)
        L[i] = A[p + i];
    /* L[0,1,2,3] = A[1,2,3,4] = [1,5,10,12] */

    for (j = 0; j < 2; j++)
        M[j] = A[q + 1 + j];
    /* M[0,1,2,3] = A[5,6] = [6,9]

Schritt 2: Aktuellen Index der Sub-Arrays und des Haupt-Arrays beibehalten

 int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 

Schritt 3: Bis wir das Ende von L oder M erreicht haben, wird das größere der L- und M-Elemente ausgewählt und an der richtigen Position an Punkt A platziert [p..r]

 while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            A[k] = L[i]; i++; 
        } 
        else { 
            A[k] = M[j]; 
            j++; 
        } 
        k++; 
    }

Schritt 4: Wenn die Elemente in L oder M aufgebraucht sind, müssen die restlichen Elemente in A platziert werden [p..r]

/* Мы вышли из предыдущего цикла, потому что j <n2 не выполняется */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

/* Мы вышли из предыдущего цикла, потому что i <n1 не выполняется */  

    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}

Dieser Schritt wäre notwendig, wenn die Größe M größer als L wäre.
Am Ende der Merge-Funktion wird das Subarray A[p..r] sortiert.