Sortiernetze

Sortiernetze sind Spezialfälle von Sortierverfahren im Allgemeinen. Sie zeichnen sich dadurch aus, dass die Vergleiche datenunabhängig durchgeführt werden. Die einzige verwendete Art von Operation ist der Vergleichs-Austausch-Schritt zwischen zwei Datenelementen: wenn a_i größer als a_j ist, dann vertausche a_i und a_j.

Sortierverfahren 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 Ordnungsrelation 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 Aⁿ.

Die folgende Definition behandelt den einfachsten Fall des aufsteigenden Sortierens von Datenfolgen.

Definition: Das Sortierproblem besteht darin, eine beliebige Datenfolge a₀, ..., a_n-1, a_i 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 Sortierverfahren auf zweidimensionalen Prozessorfeldern diese Definition verallgemeinern und die Indexmenge J = {0, ..., n-1} × {0, ..., n-1} sowie eine Sortierrichtung ρ : J Pfeil nach rechts {0, ..., |J|-1} einführen.

Vergleichernetze 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 Aⁿ angewandt wird:

Definition: Ein Vergleicher ist eine Abbildung

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

mit

[i:j](a)_i = min(a_i, a_j)

[i:j](a)_j = max(a_i, a_j)

[i:j](a)_k = a_k für alle k mit k ≠ i, k ≠ j

für alle a Element Aⁿ.

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 Pfeilrichtung 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

Wie in Bild 1 angedeutet, lassen sich Vergleicher zu Vergleichernetzen zusammenschalten.

Definition: Ein Vergleichernetz N ist eine Hintereinanderausführung von Vergleichern:

N = [i₁:j₁]· ...· [i_m:j_m] , m Element natürliche Zahlen

Bild 2 zeigt als Beispiel das Vergleichernetz

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

Bild 2: Vergleichernetz N

Bei einem Vergleichernetz 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 Vergleichernetze 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 a : N(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 Vergleicherstufe S ist eine Hintereinanderausführung von paarweise unabhängigen Vergleichern

S = [i₁:j₁]· ...· [i_r:j_r] , r Element natürliche Zahlen

Die Vergleicher innerhalb einer Vergleicherstufe können in beliebiger Reihenfolge, oder aber auch parallel ausgeführt werden. Das Vergleichernetz in Bild 2 besteht aus zwei Vergleicherstufen.

Definition: Ein Vergleichernetz heißt Standard-Vergleichernetz, 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 Vergleichernetz 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 Vergleichernetzen bezeichnen wir einen Vergleicher [i-1: i] nur durch die Zahl i. Ein primitives Vergleichernetz entspricht damit einer Folge von Zahlen aus der Menge {1, ..., n-1}.

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

Bild 3: Primitives Vergleichernetz

Definition: Ein Sortiernetz ist ein Vergleichernetz, das alle Eingabefolgen sortiert.

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

Die Frage, ob ein beliebig vorgegebenes Vergleichernetz 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 Sortierverfahren Bubblesort, Odd-even Transposition Sort, Bitonic Sort und Odd-even Mergesort, ferner auch Shellsort. Diese lassen sich als Sortiernetze realisieren.

Bubblesort und Odd-even Transposition Sort sind primitive Sortiernetze, d.h. Vergleiche finden nur zwischen benachbarten Elementen der Datenfolge statt. Primitive Sortiernetze benötigen immer Ω(n²) 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 Prozessorfeldern eignen, da die Datenkommunikation lokal ist.

Mit O(n·log(n)²) 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) Problemgrößen von über 2¹⁰⁰⁰ besser als Bitonic Sort.

In der folgenden Tabelle ist die Komplexität der erwähnten Sortiernetze zusammenfassend dargestellt. Die Anzahl der Vergleicherstufen entspricht der Zeitkomplexität, die Anzahl der Vergleicher dem Hardwareaufwand bei paralleler Implementierung. Bei sequentieller Implementierung entspricht die Anzahl der Vergleicher der Zeitkomplexität.

	Vergleicherstufen	Vergleicher
Bubblesort	Θ(`n`)	Θ(`n`²)
Odd-even Transposition Sort	Θ(`n`)	Θ(`n`²)
Bitonic Sort	Θ(log(`n`)²)	Θ(`n`·log(`n`)²)
Odd-even Mergesort	Θ(log(`n`)²)	Θ(`n`·log(`n`)²)
Shellsort	Θ(log(`n`)²)	Θ(`n`·log(`n`)²)


[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 Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, algorithmische Geometrie, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen. [Weitere Informationen]

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

Sortiernetze

Sortiernetze

Vergleichernetz

Sortiernetz

Literatur