Mergesort: Variante f ohne explizites Auslagern

 aufwärts

Bei der Standardversion des Sortierverfahrens Mergesort wird in der Funktion merge die vordere Hälfte der Datenfolge in ein Hilfsarray ausgelagert. Anschließend werden die Datenelemente der ausgelagerten Hälfte und die der hinteren Hälfte ihrer Größe nach zurückkopiert.

Es ist naheliegend, das Auslagern mit dem vorausgehenden Rekursionsschritt zu kombinieren, indem das Hilfsarray zum Zielarray der Funktion merge gemacht wird.

Idee

Die folgende Implementation [Kloe 08] verwendet zwei Funktionen sortInPlace und sortInto.

In der Funktion sortInPlace wird zunächst die hintere Hälfte des Arrays a rekursiv mit sortInPlace an Ort und Stelle sortiert, unter Benutzung des Hilfsarrays b. Anschließend wird die vordere Hälfte mit sortInto ins Hilfsarray sortiert. Dies ist die Situation wie nach dem Auslagern der vorderen Hälfte in der Standardversion von Mergesort. Zum Schluss werden mit merge die Datenelemente der ausgelagerten Hälfte und die der hinteren Hälfte ihrer Größe nach ins Array a zurückkopiert (Bild 1).

Bild 1: Funktion sortInPlace
Bild 1: Funktion sortInPlace

In der Funktion sortInto wird die vordere Hälfte des Arrays a mit sortInPlace an Ort und Stelle sortiert, unter Benutzung des Hilfsarrays b. Dann wird rekursiv mit sortInto die hintere Hälfte ins Hilfsarray sortiert. Dies ist die Situation wie nach dem Auslagern der vorderen Hälfte in der Standardversion, jedoch mit vertauschten Rollen von Array a und Hilfsarray b. Zum Schluss werden mit merge die Datenelemente ihrer Größe nach ins Hilfsarray b kopiert (Bild 2).

Bild 2: Funktion sortInto
Bild 2: Funktion sortInto

Programm

Die folgende Implementierung in C++ wird erleichtert durch die C-typische Adressierung von Arrays wie z.B. im Aufruf sortInto(a+m, b+m, n-m).

 

void sort(int* a, int n)
{
    int m=(n+1)/2;
    int* b=new int[m];    // auxiliary array
    sortInPlace(a, b, n);
}

// sorts array a of length n in-place using array b as auxiliary array
void sortInPlace(int* a, int* b, int n)
{
    if (n<=1)
        return;

    int m=(n+1)/2;    // length of first half

    // sort second half of length n-m in-place using b as auxiliary array
    sortInPlace(a+m, b, n-m);

    // sort first half of length m, put result into b
    sortInto(a, b, m);

    merge(a, b, m, n);
}

// sorts array a of length n and puts the result into array b
void sortInto(int* a, int* b, int n)
{
    if (n<=0)
        return;

    int m=(n+1)/2;    // length of first half

    // sort first half of length m in-place using b as auxiliary array
    sortInPlace(a, b, m);

    // sort second half of length n-m, put result into second half of b
    sortInto(a+m, b+m, n-m);

    merge(b, a, m, n);
}

// merges array b and the second half of array a into array a 
void merge(int* a, int* b, int m, int n)
{
    int i, j, k;
    i=0; j=m; k=0;
    while (k<j && j<n)
        if (b[i]<=a[j])
            a[k++]=b[i++];
        else
            a[k++]=a[j++];

    while (k<j)
        a[k++]=b[i++];
}

Literatur

[Kloe 08]T. Kloecker: (Persönliche Korrespondenz). Thomas Kloecker (2008)

 

 

Zurück zu Mergesort  oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©  
Valid HTML 4.01 Transitional