Sortiernetze

Optimale Sortiernetze

 aufwärts

Sortiernetze sind spezielle Sortier­verfahren, bei denen die Daten durch eine festliegende Folge von Vergleichs-Austausch-Schritten sortiert werden. Diese Vergleichs-Austausch-Schritte werden von Vergleichern durchgeführt; diese Vergleicher sind die Grund­bausteine von Sortier­netzen.

Gesucht sind Sortiernetze mit

  1. möglichst wenigen Vergleichern   bzw.
  2. möglichst wenigen Vergleicher­stufen.

Sortiernetze lassen sich systematisch entwerfen. Die Sortiernetze mit den wenigsten Vergleichern sind dabei Bitonic Sort, Odd-even Mergesort und Shellsort. Alle diese Sortiernetze enthalten Θ(n log(n)2) Vergleicher.

Sortier­verfahren wie Mergesort oder Heapsort haben lediglich eine Komplexität von Θ(n log(n)). Diese Verfahren lassen sich aber nicht als Sortiernetze implementieren, weil die durch­geführten Vergleiche daten­abhängig sind. Bei einem Sortiernetz liegen die durch­geführten Vergleiche dagegen von vorneherein fest, sind also daten­unabhängig.

Es gibt ein theoetisches Resultat, dass es auch Sortiernetze mit O(n log(n)) Vergleichern gibt [AKS 83]. Allerdings ist die Konstante, die sich hinter der O-Notation verbirgt, für jegliche praktische Verwendbar­keit bei weitem zu groß.

Daher ist es interessant, Sortiernetze mit möglichst wenigen Vergleichern (bzw. Vergleicher­stufen) zu entwerfen und dabei zu versuchen, bessere Ergebnisse als die bisher bekannten zu erzielen.

Sortiernetze mit minimaler Anzahl von Vergleichern

Als untere Schranke für die Anzahl der Vergleicher eines Sortier­netzes mit n Eingängen lässt sich die informations­theoretische untere Schranke heranziehen. Sie besagt, dass zur Unter­scheidung der n! möglichen Permutationen von n Zahlen mindestens log2(n!) Ja/Nein-Ent­scheidungen erforderlich sind. Jeder Vergleich stellt genau eine solche Ja/Nein-Entscheidung dar; daher benötigt jedes Sortiernetz mit n Eingängen mindestens log2(n!) Vergleicher.

Die folgende Tabelle zeigt die Anzahl V(n) der Vergleicher, die für Sortiernetze mit nkleiner gleich8 Eingängen höchstens erforderlich sind [Knu 73] und die Anzahl Ui(n) der Vergleicher, die aufgrund der informations­theoretischen unteren Schranke mindestens erforderlich sind.

n2345678
V(n)1359121619
Ui(n)1357101316

 

Der Wert V(n) stellt eine obere Schranke für die Anzahl der Vergleicher in einem Sortiernetz mit n Eingängen dar; seine Gültigkeit wird bewiesen, indem ein ent­sprechendes Sortiernetz angegeben wird.

Es stellt sich heraus, dass für Sortiernetze die informations­theoretische untere Schranke nicht scharf genug ist. Sie berück­sichtigt nicht die Ein­schränkung, dass bei Sortier­netzen die durch­geführten Vergleiche von vorneherein festliegen. In der Tat haben sich für n = 5, 6, 7, 8, 9, 10 die schärferen unteren Schranken U(n) = 9, 12, 16, 19, 25, 29 beweisen lassen. Damit sind die gefundenen Sortiernetze für n = 2, ..., 10 optimal. Ab n = 11 könnte es sein, dass sich noch bessere Sortiernetze finden lassen oder aber, dass sich schärfere untere Schranken beweisen lassen, oder beides.

 

Die folgenden Abbildungen zeigen ent­sprechende optimale Sortiernetze für n = 2, ..., 8 Eingänge:

Bild 1: Minimales Sortiernetz N2 für n = 2
Bild 1: Minimales Sortiernetz N2 für n = 2

 

Bild 2: Minimales Sortiernetz N3 für n = 3
Bild 2: Minimales Sortiernetz N3 für n = 3

 

Bild 3: Minimales Sortiernetz N4 für n = 4
Bild 3: Minimales Sortiernetz N4 für n = 4

 

Bild 4: Minimales Sortiernetz N5 für n = 5
Bild 4: Minimales Sortiernetz N5 für n = 5

 

Bild 5: Minimales Sortiernetz N6 für n = 6
Bild 5: Minimales Sortiernetz N6 für n = 6

 

Bild 6: Minimales Sortiernetz N7 für n = 7
Bild 6: Minimales Sortiernetz N7 für n = 7

 

Bild 7: Minimales Sortiernetz N8 für n = 8
Bild 7: Minimales Sortiernetz N8 für n = 8

Das Sortiernetz N8 ist entspricht dem Sortier­verfahren Odd-even Mergesort.

Neben den oben dar­gestellten Sortier­netzen gibt es noch eine ganze Reihe anderer Sortiernetze, die ebenfalls optimal sind. Teilweise jedoch gehen diese lediglich durch Umordnen der Eingänge aus den oben dar­gestellten Sortier­netzen hervor.

Sortiernetze mit minimaler Anzahl von Vergleicherstufen

Zwei Vergleicher [i:j] und [k:l] heißen unabhängig, wenn i, j, k, l paarweise verschieden sind. Eine Hinter­einander­ausführung von paarweise unabhängigen Vergleichern ist eine Vergleicher­stufe. Innerhalb einer Vergleicher­stufe können die Vergleicher auch parallel ausgeführt werden.

Es stellt sich daher die Frage nach Sortier­netzen mit möglichst wenigen Vergleicher­stufen. Die folgende Tabelle gibt einen Überbick über die Anzahl S(n) der Vergleicher­stufen, die in einem Sortiernetz mit n Eingängen höchstens erforderlich sind [Knu 73] sowie über die besten bekannten unteren Schranken R(n).

n2345678
S(n)1335566
R(n)1335566

 

Die oben dar­gestellten Sortiernetze sind somit auch hinsichtlich der Anzahl der Vergleicher­stufen optimal. Bei Sortier­netzen mit mehr als 8 Eingängen sind die bisher bekannten Sortiernetze mit minimaler Anzahl von Vergleichern bzw. von Vergleicher­stufen teilweise unter­schiedlich.

Literatur

[Knu 73]D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)
[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)
[BB 11]S.W. Al-Haj Baddar, K.E. Batcher: Designing Sorting Networks. Springer (2011)

 

Weiter mit:   [Minimale Sortiernetze mit 9,...,16 Eingängen]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 14.12.2014   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