Sortiernetz(werk)e

Die in diesem Programm implementierten bzw. vorgestellten Sortieralgorithmen sind flexibel, weil sie für eine prinzipiell beliebige Anzahl an Sortierelementen geeignet sind. Ist deren Anzahl hingegen bekannt oder überschreitet zumindest eine geplante Anzahl nicht (die fehlenden Sortierelemente können dann einfach durch Null- oder Maximalelemente, sog. „Dummies“, vertreten werden), können auch sog. Sortiernetzwerke oder Sortiernetze verwandt werden. Das sind funktional eingeschränkte Sortieralgorithmen, die nur auf Vergleichen und Vertauschungen (in dieser Reihenfolge kombiniert, ggf. auch zusätzlich nur Vertauschungen ohne vorherige Vergleiche, also bedingungslose Vergleiche) beruhen. Verschiebungen und Wertezwischenspeicherungen (z.B., um ein Minimum oder Maximum zu suchen) kommen in ihnen nicht vor. Diese kann man auch als Hardwarelösung mithilfe „fester Verdrahtungen“ lösen. Jedoch sind sie für  Parallelisierungen  hervorragend geeignet. Selbstredend ist ein solches Sortiernetzwerk wie jeder Sortieralgorithmus erst dann vollständig, wenn es jede beliebige Eingabemenge zuverlässig sortiert. Da die Vergleiche und Vertauschungen und mithin auch ihre Anzahl, Position und damit auch Ausführungsreihenfolge unabhängig von der Struktur der Startmenge, also auch bei erhöhten Ordnungsniveaus, von vornherein feststehen (determiniert sind), sind solche Netz(werk)e auch nicht adaptiv.

Bestimmte Sortieralgorithmen lassen sich als Sortiernetze abbilden und umgekehrt bestimmte Sortiernetzwerke (die mit einer elementeanzahlsverallgemeinerbaren Vorgehensweise) als elementeanzahlsflexible Sortieralgorithmen verallgemeinern. Das bedeutet, daß sich solche Sortiernetze für beliebige Elementeanzahlen verallgemeinern lassen und demnach einen anzahlsflexiblen Sortieralgorithmus realisieren. Manche Sortieralgorithmen lassen sich 1:1 als Sortiernetze abbilden bzw. umgekehrt (Bitonic, Bose-Nelson-, Circle-, Odd-Even- und Pairwise-Network-Mergesort, AKS,- Bubble-, Odd-Even-Transposition-, Quick- (mit (meistens) gleichgroßen Partitionen bzw. perfekter Halbierung)-, Shell-, Simple- und Zig-Zag-Sort. Einige dieser Sortieralgorithmen sind nur mit Effizienzverlust als Sortiernetze realisierbar, weil alle denkbar möglichen Vertauschungen unabhängig vom tatsächlich schon erreichten Ordnungsniveau vor dem Sortieren und während des Sortierens berücksichtigt werden müssen (z.B. Insertionsort, allerdings ist auch da die fast schon unsinnige, nichtoptimierte Variante der ersten Gruppe angehörend). Die Sortieralgorithmen der letzten Gruppe lassen sich überhaupt nicht als Sortiernetze abbilden, weil der Sortierverlauf von der Elementeanordnung abhängt (z.B. Heap- und Quicksort) oder deren Vergleiche nichtdeterminiert sind (Spin-The-Bottle- und Annealing-Sort), wobei diese Merkmale genaugenommen gemeinsam auftreten. Bemerkenswert ist, daß viele dieser Netz(werk)e Zweierpotenzen als Elementeanzahlen voraussetzen, was damit zu tun hat, daß die Sortieraufgabe mit ihnen nicht flexibel aufgespaltet werden kann.

Alle Vergleichsoperationen und nachfolgenden optionalen Vertauschungen heißen hier Vergleicher. Sortiernetzwerke, deren Vergleicher sich nur auf benachbarte Elemente beziehen, heißen primitiv (steht unter Vergleichernetzen) und sind stabil. Alle jeweils gleichzeitig ausführbaren Vergleicher bilden je eine Vergleicherstufe, das Sortiernetz läßt sich also zu deutlich weniger Vergleicherstufen im Vergleich zur Anzahl der Vergleicher verdichten. Bei maximaler Parallelisierung hängt die Sortiergeschwindigkeit demnach nur von der Anzahl der Vergleicherstufen ab. Die Anzahl aller Vergleicher wird als Größe, die maximale Anzahl Vergleicher, die ein Element während des Sortierens durchlaufen kann, als Tiefe des Sortiernetzes bezeichnet. Da diese Vergleicher sequentiell durchlaufen werden (müssen), muß die Tiefe des Sortiernetzwerkes der Anzahl der Vergleicherstufen entsprechen. Weil zudem die Anzahl der Vergleicher pro Vergleicherstufe maximal ½ n (n: Anzahl der Elemente) beträgt bzw. betragen kann, kann die Anzahl Vergleicherstufen nicht beliebig gegenüber der Anzahl der Vergleicher reduziert werden, vielmehr stellt v / (½ n) (v: Anzahl der Vergleicher) hier eine untere Schranke dar. Die Parallelisierbarkeit und mithin die Parallelität / Simultaneität lassen sich demnach nicht beliebig steigern.

Man kann beliebige Sortiernetze konstruieren, indem man einfach ein noch leeres, d.h. vergleicherloses Sortiernetz mit allen möglichen (!) Startanordnungen bestückt / beschickt und bei allen Elementeanordnungen am Ausgang, die der sortierten Ordnung zuwiderlaufen (sog. Inversionen), einen Vergleicher an das jeweilige Ende des Sortiernetzes anfügt. Es reicht dabei allerdings aus, nur zwei voneinander verschiedene Schlüsselgrößen zu verwenden (z.B. 0 und 1, deshalb das sog. 0-1-Prinzip, was die Anzahl der möglichen Startmengen von n! auf „nur“ 2ⁿ reduziert. Das ist zum einen bei größeren Anzahlen aber immer noch äußerst aufwendig, und eine Systematik im Sinne eines elementanzahlsflexiblen Sortieralgorithmus' wird dabei wahrscheinlich auch nicht entstehen, das Sortiernetzwerk also nur für (maximal) diese Elementeanzahl geeignet sein. Mir ist nicht bekannt, ob dieses 0-1-Prinzip auch auf Sortieralgorithmen, die sich nicht als Sortiernetzwerke realisieren oder abbilden lassen, verallgemeinert bzw. erweitert werden kann.

Die bevorzugte Darstellung solcher Netz(werk)e sind sog. Knuth-Diagramme. Die folgenden Bilder zeigen verschiedene Sortiernetzwerke für (bis zu) 8 Elemente. Die Zeit läuft von links nach rechts. Evtl. gibt es Sortiernetze, die auch umgekehrt („zeitinvers“) oder bei anderweitig permutierten Vergleicherstufen funktionieren; bei den Vergleichern innerhalb derselben Stufe ist die Ausführungsreihenfolge ja beliebig. Jede waagerechte Linie speichert ein Sortierelement bzw. fungiert als Platzhalter für ein solches, und die Pfeile verkörpern je einen Vergleicher. Die dicht beieinanderstehenden Pfeile sind nur der Übersichtlichkeit und Eindeutigkeit halber versetzt angeordnet; diese Operationen stellen tatsächlich je eine Vergleicherstufe dar, wovon jeder der folgenden vier Sortiernetze sechs beinhaltet:

 

Es ist ein ungelöstes Problem der theoretischen Informatik, für jede beliebige Anzahl an Eingängen bzw. Sortierelementen das optimale Sortiernetz(werk) zu finden. Zum einen wäre da die minimale Anzahl der Vergleicher und / oder Vergleicherstufen, zum anderen muß ein solches Sortiernetzwerk auch gefunden bzw. entwickelt werden. Außerdem stellte es sich als ein Zielkonflikt heraus, sowohl die Vergleicher als auch die Vergleicherstufen anzahlig zu minimieren. Ein weiteres Qualitätsmerkmal könnte sein, wie simpel die Anzahl der Elemente reduziert werden kann und ob beim Herauslösen eines einzelnen Elementes wiederum ein solches Netzwerk mit derselben Eigenschaft entsteht. Das folgende Netzwerk mit 7 Elementen kann um jeweils eines (jeweils das untere) reduziert werden und vererbt diese Eigenschaft auch an jeden seiner Nachfolger:

Flexibler in der Darstellung sind Diagramme, in denen auch die Elementekanäle flexibel(er) sind. Das folgende Schema, mit Straßenkreide hinreichend groß auf einen Untergrund gemalt, könnte sogar ein Spiel für Kinder sein („Algorithmus zum Erleben“, analog den getanzten Sortieralgorithmen). Es sortiert dann z.B. (bis zu) 6 Kinder beliebiger Reihenfolge stets, d.h. bei jeder beliebigen Startanordnung, nach dem Geschlecht, der Größe oder einem anderen Sortiermerkmal:

Auch bekannte, rein vergleichsbasierte Sortieralgorithmen lassen sich per Sortiernetzwerke abbilden bzw. realisieren (s.o.) und mithin für beliebige Anzahlen verallgemeinern:

Hieraus läßt sich einiges erkennen:

• Bubble- und Insertionsort funktionieren in gewisser Weise invers (so wie z.B. Merge- und Quicksort).
• Beide sind  stabil , da sie nur benachbarte Sortierelemente vergleichen und ggf. tauschen.
• Werden beide Algorithmen maximal parallelisiert, verschmelzen sie zu einem Algorithmus.
• Beide haben quadratische Komplexität (die Anzahl der Vergleiche(r) wächst (annähernd) mit ½ n²).