Sortierverfahren

Natural Mergesort

 aufwärts

Idee

Natural Mergesort ist eine Variante des iterativen Mergesort-Verfahrens. Der Grundgedanke besteht darin, in der zu sortierenden Folge "natürlich" vorkommende, bereits sortierte Teilstücke auszunutzen.

Beispiel:  In der Zahlenfolge

6 8 2 4 1 3 5 7

sind folgende bereits sortierte Teilstücke enthalten:

6 8,   2 4  und   1 3 5 7.

Mergesort dagegen nimmt keine Rücksicht auf bestehende Vor­sortierungen, sondern durch­läuft stets alle log(n) Iterations­ebenen. In dem Beispiel etwa würden auf der ersten Ebene die 6 und die 8 zu dem sortierten Teilstück 6 8 verschmolzen, obwohl dieses Teilstück auch vorher schon sortiert war.

Durch das Ausnutzen bestehender Vor­sortierungen lassen sich bei Natural Mergesort gegebenenfalls Merge-Schritte einsparen. Im besten Fall, wenn die Folge nur aus konstant vielen sortierten Teilstücken besteht, sind nur konstant viele Merge-Schritte erforderlich, so dass sich eine Zeit­komplexität von Θ(n) ergibt. Im schlechtesten Fall hat Natural Mergesort allerdings dieselbe Zeit­komplexität wie Mergesort, nämlich Θ(n log(n)).

 

Implementierung

Um die Implementierung zu vereinfachen, werden ähnlich wie bei der Variante c von Mergesort jeweils gegenläufig sortierte Teilstücke verschmolzen. Dies hat zusätzlich den Vorteil, dass auch absteigend vorsortierte Teilstücke ausgenutzt werden können.

Definition:  Sei a = a0, ..., an-1 eine Folge. Ein Teilstück ai, ..., ai+k, k Element natürliche Zahlen0 heißt bitonischer Lauf, wenn es ein m Element natürliche Zahlen0, mkleiner gleichk  gibt, so dass gilt

aikleiner gleichai+1kleiner gleich ... kleiner gleichai+mgrößer gleichai+m+1größer gleich ... größer gleichai+k.

Ein bitonischer Lauf ist also ein Teilstück, das zuerst monoton steigt und dann monoton fällt (daher bitonisch). Aber auch ein rein monoton steigendes Teilstück ist ein bitonischer Lauf (bei dem m = k ist), ebenso ein rein monoton fallendes Teilstück (m = 0).

Beispiel:  Die Zahlenfolge

6 8 2 4 1 3 5 7

hat die bitonischen Läufe

6 8 2,   4 1   und   3 5 7.

In der folgenden Implementation von Natural Mergesort werden im ersten Schritt die vorhandenen bitonischen Läufe ausfindig gemacht. In den weiteren Iterations­schritten werden diese abwechselnd zu aufsteigend bzw. absteigend sortierten Teilstücken verschmolzen, so dass hierdurch wiederum, nunmehr längere, bitonische Läufe zustande kommen. Am Ende ist die gesamte Folge sortiert.

 

Programm

Genau wie Mergesort benötigt auch Natural Mergesort ein zusätzliches Array b. Die Funktion mergeruns sucht bitonische Läufe im Array a und verschmilzt sie zu sortierten Teilstücken. Diese Teilstücke werden abwechselnd aufsteigend und absteigend sortiert in das Array b geschrieben, so dass dort neue bitonische Läufe entstehen. Die Funktion gibt true zurück, wenn das ganze Array b aufsteigend sortiert ist.

Die Prozedur merge verschmilzt einen bitonischen Lauf zu einem sortierten Teilstück. Der Parameter asc bestimmt die Sortier­richtung.

Die Prozedur naturalmergesort ruft solange mergeruns auf, bis die Folge sortiert ist. Hierbei wechseln die Rollen des ursprünglichen Arrays a und des Hilfsarrays b sich ab.

Die folgende Klasse NaturalMergeSorter kapselt die genannten Funktionen. Die Methode sort übergibt das zu sortierende Array an das Array a und ruft naturalmergesort auf.

Mit der Anweisung

NaturalMergeSorter s=new NaturalMergeSorter();

wird ein Objekt vom Typ NaturalMergeSorter angelegt. Mit

s.sort(c);

kann anschließend ein Array c sortiert werden.

Es folgt das Programm. In Java bedeutet die bedingte Zuweisung c=asc? 1: -1; dasselbe wie if (asc) c=1; else c=-1;. Die Anweisung x=a[i++]; ist äquivalent zu der Anweisungs­folge x=a[i]; i=i+1;. Die Kurz­schreibweise k+=c; bedeutet k=k+c;.

 

public class NaturalMergeSorter
{
    private int[] a;
    private int[] b;    // Hilfsarray
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        b=new int[n];
        naturalmergesort();
    }

    private boolean mergeruns(int[] a, int[] b)
    {
        int i=0, k=0, x;
        boolean asc=true;

        while (i<n)
        {
            k=i;
            do x=a[i++]; while (i<n && x<=a[i]);  // aufsteigender Teil
            while (i<n && x>=a[i]) x=a[i++];      // absteigender Teil
            merge (a, b, k, i-1, asc);
            asc=!asc;
        }
        return k==0;
    }

    private void merge(int[] a, int[] b, int lo, int hi, boolean asc)
    {
        int k=asc? lo: hi;
        int c=asc? 1: -1;
        int i=lo, j=hi;

        // jeweils das nächstgrößte Element zurückkopieren,
        // bis i und j sich überkreuzen
        while (i<=j)
        {
            if (a[i]<=a[j])
                b[k]=a[i++];
            else
                b[k]=a[j--];
            k+=c;
        }
    }

    private void naturalmergesort()
    {
        // abwechselnd von a nach b und von b nach a verschmelzen
        while (!mergeruns(a, b) & !mergeruns(b, a));
    }

}    // end class NaturalMergeSorter

In dieser Implementierung werden die bitonischen Läufe durch mergeruns jedesmal neu gesucht. Dies ist eigentlich nur beim ersten Mal notwendig, danach sind die jeweils neu gebildeten bitonischen Läufe ja bekannt. Man könnte ihre Anfangs-Index­positionen in einer Warteschlange (Queue) für den nächsten Durchlauf von mergeruns speichern. Die asymptotische Zeit­komplexität ändert sich allerdings hierdurch nicht.

 

Analyse

Die Funktion mergeruns halbiert bei jedem Durchlauf die Anzahl der bitonischen Läufe. Sind zu Anfang r natürliche Läufe vorhanden, so sind damit Θ(log r) Aufrufe erforderlich, bis nur noch ein Lauf übrig ist. Da mergeruns in Zeit Θ(n) läuft, hat Natural Mergesort eine Zeit­komplexität von Θ(n log r).

Der schlechteste Fall tritt ein, wenn alle natürlich vorkommenden bitonischen Läufe die Länge 2 haben, z.B. wie in der Folge 1 0 1 0 1 0 1 0. Dann sind r = n/2 Läufe vorhanden, und Natural Mergesort benötigt genauso viel Zeit wie Mergesort, nämlich Θ(n log(n)).

Der günstigste Fall tritt ein, wenn die Folge nur aus konstant vielen bitonischen Läufen besteht. Dann ist nur Θ(n) Zeit erforderlich. Insbesondere ist dies der Fall, wenn die Folge bereits aufsteigend sortiert ist, wenn sie absteigend sortiert ist, wenn sie aus zwei sortierten Teilstücken besteht, oder wenn konstant viele Elemente in eine sortierte Folge einsortiert werden sollen.

Nachteilig ist, dass Natural Mergesort ebenso wie Mergesort einen zusätzlichen Speicher­platz­bedarf von Θ(n) für das temporäre Array b hat.

 

Literatur

[Knu 73]D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Natural Mergesort und andere Sortierverfahren, so etwa Quicksort, Heapsort und Shellsort, finden Sie auch in meinem Buch über Algorithmen.
Weiterevertikaler Abstand Themen des Buches: Textsuche, Graphen­algorithmen, Arithmetik, algorithmische Geometrie, Codierung, Kryptografie, parallele Sortier­algorithmen.
[Weitere Informationen]

Buch  

 

 

Weiter mit:   [Shellsort]   oder   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 11.03.2001   Updated: 05.09.2012
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik