Sortiernetze

Minimale Sortiernetze mit mehr als 8 Eingängen

 aufwärts

Sortiernetze mit minimaler Anzahl von Vergleichern

Wir hatten zunächst minimale Sortiernetze mit bis zu n = 8 Eingängen betrachtet.

Die folgende Tabelle zeigt die Anzahl V(n) der Vergleicher, die für Sortiernetze mit n > 8 Eingängen höchstens erforderlich sind [Knu 73]. Der Wert V(n) für n = 13 hat sich gegenüber 46 in [Knu 73] inzwischen auf 45 verbessert.

Die unteren Schranken U(n) haben sich gegenüber den bisher bekannten Angaben in [BB 11] erst kürzlich verbessert, dadurch dass U(9) = 25 bewiesen wurde [CCFS 14]. Wegen U(n+1) größer gleich U(n) + ceiling auflog2(n)ceiling zu haben sich die unteren Schranken ab n = 10 entsprechend verschoben. Damit sind die Sortiernetze N9 und N10 optimal.

 

n910111213141516
V(n)2529353945515660
U(n)2529333741454953

 

 

Die folgenden Abbildungen zeigen die ent­sprechenden (bisher bekannten) minimalen Sortiernetze mit n > 8 Eingängen:

Bild 1: Minimales Sortiernetz N9 für n = 9
Bild 1: Minimales Sortiernetz N9 für n = 9
Bild 2: Minimales Sortiernetz N10 für n = 10
Bild 2: Minimales Sortiernetz N10 für n = 10
Bild 3: Minimales Sortiernetz N11 für n = 11
Bild 3: Minimales Sortiernetz N11 für n = 11
Bild 4: Minimales Sortiernetz N12 für n = 12
Bild 4: Minimales Sortiernetz N12 für n = 12
Bild 5: Minimales Sortiernetz N13 für n = 13
Bild 5: Minimales Sortiernetz N13 für n = 13
Bild 6: Minimales Sortiernetz N16 für n = 16
Bild 6: Minimales Sortiernetz N16 für n = 16

Die Sortiernetze N14 und N15 entstehen durch Ein­schränkung von N16 auf die oberen 14 bzw. 15 Eingänge.

Es gibt eine ganze Reihe anderer minimaler Sortiernetze für die jeweilige Anzahl n von Eingängen. Teilweise ergeben sich diese jedoch lediglich durch Umordnen der Eingänge aus den oben dar­gestellten Sortier­netzen.

Sortiernetze mit minimaler Anzahl von Vergleicherstufen

Die folgende Tabelle gibt für n > 8 einen Überblick über die Anzahl S(n) der Vergleicher­stufen, die in einem Sortiernetz mit n Eingängen höchstens erforderlich sind [Knu 73]. Gleichzeitig stellen die Werte von S(n) auch untere Schranken für die Anzahl der Vergleicher­stufen dar; diese Tatsache ist erst kürzlich bewiesen worden [BZ 14]. Hinsichtlich der Anzahl der Vergleicher­stufen sind die unten dar­gestellten Sortiernetze somit optimal.

n910111213141516
S(n)77889999

 

In den folgenden Abbildungen sind ent­sprechende Sortiernetze mit (bisher bekannter) minimaler Anzahl von Vergleicher­stufen dargestellt, soweit sie weniger Vergleicher­stufen haben als die oben dar­gestellten Sortiernetze N9, ..., N16.

Bild 7: Sortiernetz M10 mit minimaler Anzahl von Vergleicherstufen für n = 10
Bild 7: Sortiernetz M10 mit minimaler Anzahl von Vergleicherstufen für n = 10

 

Bild 8: Sortiernetz M12 mit minimaler Anzahl von Vergleicherstufen für n = 12
Bild 8: Sortiernetz M12 mit minimaler Anzahl von Vergleicherstufen für n = 12

 

Bild 9: Sortiernetz M16 mit minimaler Anzahl von Vergleicherstufen für n = 16
Bild 9: Sortiernetz M16 mit minimaler Anzahl von Vergleicherstufen für n = 16

 

Wiederum entstehen die Sortiernetze M13, M14 und M15 durch Ein­schränkung von M16 auf die oberen 13, 14 bzw. 15 Eingänge.

Sortiernetze mit mehr als 16 Eingängen

Die folgenden Tabellen geben Auskunft über die bisher bekannten oberen Schranken V(n) und unteren Schanken U(n) für die Anzahl der Vergleicher eines Sortier­netzes mit n Eingängen, ferner über die bisher bekannten oberen Schranken S(n) und unteren Schranken R(n) für die Anzahl der Vergleicher­stufen [BB 11], [BZ 14].

n17181920212223242526272829303132
V(n)73808893103110118123133140150156165172180185
U(n)586368737883889398103108113118123128133

Anzahl der Vergleicher: obere und untere Schranken

 

n17181920212223242526272829303132
S(n)11111212121213131414141414141414
R(n)9999999999999999

Anzahl der Vergleicher­stufen: obere und untere Schranken

 

Literatur

[BB 11]S.W. Al-Haj Baddar, K.E. Batcher: Designing Sorting Networks. Springer (2011)
[BZ 14]D. Bundala, J. Závodný: Optimal Sorting Networks. In: A.H. Dediu et al. (Hrsg.): Lecture Notes in Computer Science 8370, 236-247 (2014)
[CCFS 14]M. Codish, L. Cruz-Filipe, M. Frank, P. Schneider-Kamp: Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten). arXiv:1405.5754 (2014)
[Knu 73]D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 14.12.2014   Updated: 03.03.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
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