Sortiernetze

Sortiernetze

 English version  aufwärts

Sortiernetze sind Spezialfälle von Sortier­verfahren im allgemeinen. Sie zeichnen sich dadurch aus, dass die Vergleiche daten­unabhängig durchgeführt werden. Die einzige verwendete Art von Operation ist der Vergleichs-Austausch-Schritt zwischen zwei Daten­elementen: wenn ai größer als aj ist, dann vertausche ai und aj.

Sortier­verfahren dieser Art lassen sich leicht parallelisieren und gegebenenfalls in Hardware realisieren.

Definition:  Sei J = {0, ..., n-1} eine Indexmenge und A eine Menge von Daten mit einer Ordnungs­relation kleiner gleich. Eine Datenfolge ist eine Abbildung a : J Pfeil nach rechts A, also eine Folge der Länge n von Daten. Die Menge aller Datenfolgen der Länge n über A bezeichnen wir mit An.

Die folgende Definition behandelt den einfachsten Fall des auf­steigenden Sortierens von Datenfolgen.

Definition:  Das Sortier­problem besteht darin, eine beliebige Datenfolge a0, ..., an-1,  ai Element A so zu einer Folge aφ(0), ..., aφ(n-1) umzuordnen, dass gilt:

aφ(i) kleiner gleich aφ(j)   für   i < j.

Hierbei ist φ eine Permutation der Indexmenge  J = {0, ..., n-1}.

Später werden wir im Zusammenhang mit Sortier­verfahren auf zwei­dimensionalen Prozessor­feldern diese Definition verall­gemeinern und die Indexmenge J = {0, ..., n-1} × {0, ..., n-1} sowie eine Sortier­richtung  ρ : J Pfeil nach rechts {0, ..., |J|-1} einführen.

Vergleichernetz

Vergleicher­netze wurden informell in [Knu 73] und für den Fall J = {0, ..., n-1} eingeführt. Ein Vergleicher [i:j] bringt das i-te und das j-te Datenelement einer Folge in aufsteigende Reihenfolge. Formal ist ein solcher Vergleicher eine Abbildung, die auf die Datenfolge a Element An angewandt wird:

Definition:  Ein Vergleicher ist eine Abbildung

[i:j] : An Pfeil nach rechts An,   i, j Element {0, ..., n-1}

mit

[i:j](a)i  =  min(ai, aj)

[i:j](a)j  =  max(ai, aj)

[i:j](a)k  =  ak  für alle k mit  k ≠ ik ≠ j

für alle a Element An.

Vergleicher werden grafisch als Pfeile dargestellt (Bild 1). Dabei ist die Vorstellung, dass die Datenfolge von links nach rechts entlang der waagerechten Linien wandert. Elemente der Datenfolge, die dabei auf einen Vergleicher treffen, werden in Pfeil­richtung sortiert. In Bild 1 wandert die Datenfolge 6 8 5 1 an den Linien entlang und trifft dabei nacheinander auf die zwei Vergleicher [1:3] und [2:1].

Bild 1: Umordnen einer Datenfolge durch Vergleicher
Bild 1: Umordnen einer Datenfolge durch Vergleicher

Wie in Bild 1 angedeutet, lassen sich Vergleicher zu Vergleicher­netzen zusammen­schalten.

Definition:  Ein Vergleicher­netz N ist eine Hinter­einanderausführung von Vergleichern:

N  =  [i1:j1]· ...· [im:jm] ,   m Element natürliche Zahlen

Bild 2 zeigt als Beispiel das Vergleicher­netz

N  =  [0:2] · [1:3] · [0:1] · [2:3]

Bild 2: Vergleichernetz N
Bild 2: Vergleichernetz N

Bei einem Vergleicher­netz kommt es im allgemeinen auf die Reihenfolge der Vergleicher an. Wenn jedoch zwei aufeinander folgende Vergleicher keine waagerechte Linie gemeinsam haben, wie zum Beispiel in Bild 2 die Vergleicher [0:2] und [1:3] oder die Vergleicher [0:1] und [2:3], so können sie offenbar auch in umgekehrter Reihenfolge ausgeführt werden; die von ihnen bewirkte Abbildung bleibt dieselbe.

Definition:  Zwei Vergleicher­netze N und M sind äquivalent, wenn sie dieselbe Abbildung bewirken, d.h. wenn sie jede Eingabefolge a in jeweils dieselbe Ausgabefolge überführen:

N  kongruent  M  genau dann wenn   für alle aN(a) = M(a)

Definition:  Zwei Vergleicher [i:j] und [k:l] heißen unabhängig, wenn sie keine Linie gemeinsam haben, d.h. wenn i, j, k, l paarweise verschieden sind.

Satz:  Für zwei unabhängige Vergleicher [i:j] und [k:l] gilt

[i:j] · [k:l]   kongruent   [k:l] · [i:j]

Definition:  Eine Vergleicher­stufe S ist eine Hinter­einanderausführung von paarweise unabhängigen Vergleichern

S  =  [i1:j1]· ...· [ir:jr] ,   r Element natürliche Zahlen

Die Vergleicher innerhalb einer Vergleicher­stufe können in beliebiger Reihenfolge, oder aber auch parallel ausgeführt werden. Das Vergleicher­netz in Bild 2 besteht aus zwei Vergleicher­stufen.

Definition:  Ein Vergleicher­netz heißt Standard-Vergleicher­netz, wenn alle Vergleicher von oben nach unten gerichtet sind, d.h. wenn für alle Vergleicher [i:j] gilt, dass i < j ist.

Definition:  Ein Vergleicher­netz heißt primitiv, wenn alle Vergleicher von der Form [i-1: i] sind, d.h. wenn die Vergleicher alle zwischen benachbarten waagerechten Linien liegen und von oben nach unten zeigen.

Bei primitiven Vergleicher­netzen bezeichnen wir einen Vergleicher [i-1: i] nur durch die Zahl i. Ein primitives Vergleicher­netz entspricht damit einer Folge von Zahlen aus der Menge {1, ..., n-1}.

Beispiel:  Folgendes Vergleicher­netz N ist primitiv (Bild 3). Es kann daher durch N = 1 2 4 1 3 bezeichnet werden.

Bild 3: Primitives Vergleichernetz
Bild 3: Primitives Vergleichernetz

Sortiernetz

Definition:  Ein Sortiernetz ist ein Vergleicher­netz, das alle Eingabe­folgen sortiert.

Das Vergleicher­netz aus Bild 2 ist kein Sortiernetz, weil es z.B. die Folge 3 1 4 2 nicht sortiert.

Die Frage, ob ein beliebig vorgegebenes Vergleicher­netz ein Sortiernetz ist oder nicht, ist im allgemeinen nicht leicht zu beantworten, das Problem ist NP-schwer. Unabhängig davon lassen sich natürlich Sortiernetze systematisch konstruieren und beweisen.

Beispiele hierfür sind die in den folgenden Seiten angegebenen Sortier­verfahren Bubblesort, Odd-even Trans­position Sort, Bitonic Sort und Odd-even Mergesort, ferner auch Shellsort. Diese lassen sich als Sortiernetze realisieren.

Bubblesort und Odd-even Trans­position Sort sind primitive Sortiernetze, d.h. Vergleiche finden nur zwischen benachbarten Elementen der Datenfolge statt. Primitive Sortiernetze benötigen immer Ω(n2) Vergleicher zum Sortieren von n Daten. Die Bedeutung dieser Verfahren liegt darin, dass sie sich sehr gut für eine parallele Implementierung in Hardware oder auf Prozessor­feldern eignen, da die Daten­kommunikation lokal ist.

Mit O(n·log(n)2) Vergleichern wesentlich effizientere, wenn auch nicht optimale Sortiernetze sind Bitonic Sort, Odd-even Mergesort und Shellsort. Ein mit einer Komplexität von O(n log(n)) asymptotisch optimales Sortiernetz existiert [AKS 83]; es ist jedoch aufgrund seiner hohen Konstanten erst für (unrealistische) Problem­größen von über 21000 besser als Bitonic Sort.

In der folgenden Tabelle ist die Komplexität der erwähnten Sortiernetze zusammenfassend dargestellt. Die Anzahl der Vergleicher­stufen entspricht der Zeit­komplexität, die Anzahl der Vergleicher dem Hardware­aufwand bei paralleler Implementierung. Bei sequentieller Implementierung entspricht die Anzahl der Vergleicher der Zeit­komplexität.

 

 Vergleicher­stufen Vergleicher
Bubblesort Θ(n) Θ(n2)
Odd-even Trans­position Sort Θ(n) Θ(n2)
Bitonic Sort Θ(log(n)2) Θ(n·log(n)2)
Odd-even Mergesort Θ(log(n)2) Θ(n·log(n)2)
Shellsort Θ(log(n)2) Θ(n·log(n)2)

 

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)
[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)

Ein Kapitel über Sortiernetze finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, algorithmische Geometrie, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Bubblesort]   [0-1-Prinzip]  oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.03.1997   Updated: 04.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen 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 Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik