Sortiernetze

Bitonic Sort

 English version  aufwärts

Das Sortier­verfahren Bitonic Sort [Bat 68] ist eines der schnellsten Sortiernetze. Bei einem Sortiernetz [Knu 73] [CLRS 01] ist die Reihenfolge der Vergleiche nicht von den Daten abhängig, anders als bei Sortier­verfahren wie z.B. Quicksort oder Heapsort. Das Verfahren ist daher besonders für eine Implementierung in Hardware geeignet. Es ist darüber hinaus Grundlage vieler paralleler Sortier­verfahren auf zwei­dimensionalen Prozessor­feldern.

Das Sortiernetz Bitonic Sort enthält Θ(n log(n)2) Vergleicher. Es hat damit dieselbe asymptotische Komplexität wie die Sortiernetze Odd-even Mergesort und Shellsort. Zwar gibt es ein Sortiernetz mit nur O(n log(n)) Vergleichern [AKS 83], dieses ist jedoch aufgrund seiner hohen Konstante für alle praktischen Problem­größen langsamer als Bitonic Sort.

Im Folgenden wird das Sortiernetz Bitonic Sort auf Basis des 0-1-Prinzips entwickelt. Das 0-1-Prinzip besagt, dass ein Vergleicher­netz, das alle Folgen von Nullen und Einsen sortiert, ein Sortiernetz ist, d.h. es sortiert dann auch jede Folge von beliebigen Eingabe­werten.

Grundlagen

Definition:  Eine Folge a = a0, ..., an-1  mit  ai Element {0, 1},  i = 0, ..., n-1 heißt 0-1-Folge.

Eine 0-1-Folge heißt bitonisch,1) wenn sie höchstens zwei Wechsel zwischen 0 und 1 enthält, d.h. wenn Zahlen  k, m Element {1, ..., n} existieren derart dass

a0, ..., ak-1 = 0 ,     ak, ..., am-1 = 1 ,     am, ..., an-1 = 0   oder
a0, ..., ak-1 = 1 ,     ak, ..., am-1 = 0 ,     am, ..., an-1 = 1.

In folgendem Bild 1 sind verschiedene Beispiele bitonischer 0-1-Folgen schematisch dargestellt (Nullen weiß, Einsen grau):

Bild 1: Verschiedene Beispiele bitonischer 0-1-Folgen
Bild 1: Verschiedene Beispiele bitonischer 0-1-Folgen

Definition:  Sei n Element natürliche Zahlen, n gerade. Das Vergleicher­netz Bn ist wie folgt definiert:

Bn  =  [0 : n/2]  [1 : n/2+1]  ...  [n/2-1 : n-1].

Als Beispiel ist in Bild 2 das Vergleicher­netz B8 dargestellt.

Bild 2: Vergleichernetz B8
Bild 2: Vergleichernetz B8

Satz:  Sei n Element natürliche Zahlen, n gerade und a = a0, ..., an-1 eine bitonische 0-1-Folge. Die Anwendung des Vergleicher­netzes Bn auf a ergibt dann

Bn(a)   =  b0, ..., bn/2-1  c0, ..., cn/2-1,

wobei die bi die kleineren Elemente und die cj die größeren Elemente sind, d.h.

bikleiner gleichcj  für alle  i, j  Element {0, ..., n/2-1},

und darüber hinaus gilt

b0, ..., bn/2-1  ist bitonische 0-1-Folge   und

c0, ..., cn/2-1   ist bitonische 0-1-Folge.

Beweis:  Sei a = a0, ..., an-1 eine bitonische 0-1-Folge. Schreibt man a in zwei Zeilen, dann ergibt sich folgendes Bild (Nullen sind wieder weiß, Einsen grau dargestellt). Die Folge beginnt mit Nullen, dann kommen Einsen und dann wieder Nullen (Bild 3a). Oder die Folge beginnt mit Einsen, dann kommen Nullen und dann wieder Einsen (Bild 3b).

Es sind noch eine ganze Reihe anderer Variationen möglich, einige sind in Bild 4 dargestellt. Eine Anwendung des Vergleicher­netzes Bn entspricht einem Vergleich zwischen oberer und unterer Zeile; hierdurch wird in allen Fällen die im Satz angegebene Form hergestellt, d.h. alle bi sind kleiner oder gleich allen cj und b ist bitonisch und c ist bitonisch.

Bitonische 0-1-Folge Bitonische 0-1-Folge
(a) (b)
Bild 3: Bitonische 0-1-Folgen (dargestellt jeweils in zwei Zeilen)
Bild 4: Anwendung des Vergleichernetzes Bn auf bitonische 0-1-Folgen   
Bild 4: Anwendung des Vergleichernetzes Bn auf bitonische 0-1-Folgen   

Sortiernetz BitonicSort

Vergleicher­netze Bk für verschiedene Zweier­potenzen k bilden die Bausteine für das Sortiernetz BitonicSort(n). Durch Anwendung des Divide-and-Conquer-PrinzipsErklärung werden Vergleicher­netze BitonicMerge und BitonicSort konstruiert.

Das Vergleicher­netz BitonicMerge(n) sortiert eine bitonische Folge. Aufgrund der Tatsache, dass Bn wiederum bitonische Teilfolgen halber Länge liefert, von denen die erste die kleineren Elemente enthält und die zweite die größeren, lässt es sich rekursiv aufbauen (Bild 5).

Die bitonische Folge, die als Eingabe für BitonicMerge notwendig ist, wird aus einer aufsteigend sortierten und einer absteigend sortierten Hälfte zusammen­gesetzt. Diese sortierten Hälften werden durch rekursive Anwendung von BitonicSort erzeugt (Bild 6).

Bild 5: BitonicMerge(n)
Bild 5: BitonicMerge(n)
Bild 6: BitonicSort(n)
Bild 6: BitonicSort(n)

Im darauf folgenden Bild 7 ist als Beispiel das Sortiernetz BitonicSort(8) dargestellt.

Auf das ganze Vergleicher­netz lässt sich das 0-1-Prinzip anwenden: da das Vergleicher­netz BitonicSort beliebige 0-1-Folgen sortiert, sortiert es auch jede beliebige andere Folge, ist also ein Sortiernetz.

Bild 7: Sortiernetz BitonicSort für n=8
Bild 7: Sortiernetz BitonicSort für n=8

Analyse

Das Vergleicher­netz BitonicMerge(n) besteht aus log(n) Vergleicher­stufen (so etwa die letzten 3 = log(8) Vergleicher­stufen in Bild 7). Die Anzahl der Vergleicher­stufen T(n) des gesamten Sortier­netzes BitonicSort(n) ergibt sich also wie folgt:

T(n) = log(n) + T(n/2)  sowie

T(1) = 0.

Die Lösung dieser Rekursions­gleichung ist

T(n) = log(n) + log(n)-1 + log(n)-2 + ... + 1 = log(n)·(log(n)+1) / 2.

Jede Vergleicher­stufe des Sortier­netzes besteht aus n/2 Vergleichern; insgesamt sind dies also Θ(n log(n)2) Vergleicher.

Programm

Es folgt eine Implementation von Bitonic Sort in Java. Das Verfahren ist in der Klasse BitonicSorter gekapselt. Die Methode sort übergibt das zu sortierende Array an das Array a und ruft bitonicSort auf.

Die Funktion bitonicSort erzeugt zunächst eine bitonische Folge, indem sie die beiden Hälften der Folge gegenläufig sortiert (durch zwei rekursive Aufrufe von bitonicSort). Danach sortiert sie die bitonische Folge durch Aufruf von bitonicMerge.

Die Funktion bitonicMerge sortiert rekursiv eine bitonische Folge a. Die zu sortierende Folge beginnt am Index lo, die Anzahl der Elemente ist n, die Sortier­richtung ist aufsteigend, wenn dir = ASCENDING, sonst absteigend.

Ein Vergleicher wird durch die Funktion compare modelliert. Der Parameter dir gibt die Sortier­richtung an. Die Elemente a[i] und a[j] werden vertauscht, wenn dir = ASCENDING und (a[i] > a[j]) = true oder wenn dir = DESCENDING und (a[i] > a[j]) = false gilt.

Mit den Anweisungen

BitonicSorter s=new BitonicSorter();
s.sort(b);

wird ein Objekt vom Typ BitonicSorter erzeugt und anschließend die Methode sort aufgerufen, um ein Array b zu sortieren. Die Länge n des Arrays muss eine Zweierpotenz sein (vgl. Bitonic Sort für beliebiges n).

 

public class BitonicSorter
{
    private int[] a;
    // sorting direction:
    private final static boolean ASCENDING=true, DESCENDING=false;

    public void sort(int[] a_)
    {
        a=a_;
        bitonicSort(0, a.length, ASCENDING);
    }

    private void bitonicSort(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            bitonicSort(lo, m, ASCENDING);
            bitonicSort(lo+m, m, DESCENDING);
            bitonicMerge(lo, n, dir);
        }
    }

    private void bitonicMerge(int lo, int n, boolean dir)
    {
        if (n>1)
        {
            int m=n/2;
            for (int i=lo; i<lo+m; i++)
                compare(i, i+m, dir);
            bitonicMerge(lo, m, dir);
            bitonicMerge(lo+m, m, dir);
        }
    }

    private void compare(int i, int j, boolean dir)
    {
        if (dir==(a[i]>a[j]))
            exchange(i, j);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}    // end class BitonicSorter

Visualisierung

 

(Java-Applet zur Visualisierung von Bitonic Sort)

Zusammenfassung

Mit Θ(n log(n)2) Vergleichern ist das Verfahren Bitonic Sort nicht optimal – die untere Schranke für Sortier­verfahren, die auf Vergleichen beruhen, liegt bei Ω(n log(n)) und wird z.B. von Heapsort auch erreicht. Dennoch ist Bitonic Sort insbesondere für Hardware- und Parallel­rechner-Realisierungen interessant, da die Reihenfolge der Vergleiche von vornherein festliegt und nicht von den Daten abhängig ist.

Das Verfahren lässt sich auch für beliebiges n, das keine Zweierpotenz ist, anpassen (Bitonic Sort für beliebiges n).

Literatur

[AKS 83]M. Ajtai, J. Komlos, E. Szemeredi: An O(n log n) Sorting Network. Proceedings of the 25th ACM Symposium on Theory of Computing, 1-9 (1983)
[Bat 68]K.E. Batcher: Sorting Networks and their Applications. Proc. AFIPS Spring Joint Comput. Conf., Vol. 32, 307-314 (1968)
[CLRS 01]T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)
[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)

Bitonic Sort und andere Sortiernetze, wie etwa Odd-even Mergesort, sowie die Sortierverfahren Quicksort, Heapsort, Mergesort und Shellsort, finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: parallele Sortieralgorithmen, Textsuche, Graphenalgorithmen, algorithmische Geometrie, Arithmetik, Codierung, Kryptografie, NP-Vollständigkeit, formale Verifikation.

[Weitere Informationen]

Buch  

1)  von engl. bitonic = zweifach monotonic

 

Weiter mit:   up

 

homeH.W. Lang   Fachhochschule Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 02.02.1997   Updated: 05.02.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Angewandte Informatik

mit Schwerpunkten auf Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik