SortiernetzeSortiernetze | ![]() ![]() |
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 ai größer als aj ist, dann vertausche ai und aj.
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 . Eine Datenfolge ist eine Abbildung a : J
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 aufsteigenden Sortierens von Datenfolgen.
Definition: Das Sortierproblem besteht darin, eine beliebige Datenfolge a0, ..., an-1, ai A so zu einer Folge aφ(0), ..., aφ(n-1) umzuordnen, dass gilt:
aφ(i) 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 {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 An angewandt wird:
Definition: Ein Vergleicher ist eine Abbildung
[i:j] : An An, i, j
{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 ≠ i, k ≠ j
für alle a 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 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 = [i1:j1]· ...· [im:jm] , m
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 M
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] [k:l] · [i:j]
Definition: Eine Vergleicherstufe S ist eine Hintereinanderausführung von paarweise unabhängigen Vergleichern
S = [i1:j1]· ...· [ir:jr] , r
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 Ω(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 Prozessorfeldern eignen, da die Datenkommunikation 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) Problemgröß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 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) | Θ(n2) | ||
Odd-even Transposition 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) |
Weiter mit: [Bubblesort] [0-1-Prinzip] oder
![]() |
![]() |
![]() |
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
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: