Sortiernetze Optimale Sortiernetze

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

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)²) 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 log₂(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 log₂(n!) Vergleicher.

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

 

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:

 

 

 

 

 

 

Das Sortiernetz N₈ 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 Überblick ü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).

 

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

 

H.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 14.12.2014   Updated: 07.06.2018