Ungerade-Gerade-Vertauschungs-Sortierung

Bei die Aktivität “Weltgrößte Sortiernetzwerk” wird ein Sortiernetzwerk benutzt, die in berühmtem Buch “The Art of Computer Programming” von Donald Knuth erwähnt wird. Knuth nannte dieses Netzwerk “Ungerade-Gerade-Vertauschungs-Sortierung”. Dort er gibt auch eine Formel zur Berechnung der Anzahl der Vergleichsknoten an: (1/2)n(n-1)

Bei n Eingangsknoten besitzt es n Vergleichsebenen mit insgesamt (1/2)n(n-1) Vergleichsknoten, plus n Eingangsknoten und n Ausgangsknoten.

Für n=50 ergibt das 1325 Knoten

Für n=25 ergibt das 350 Knoten

Für n=25 ergibt das 252 Knoten

Knuth zeichnet Sortier-Netzwerke so, dass jeder Vergleich durch 2 Knoten dargestellt wird und es keine Knoten für Ein-/Ausgaben gibt.

Das gibt:

n=50 -> 2450 Knoten
n=21 -> 420 Knoten
n=25 -> 600 Knoten

Donald Knuth

Seit einem halben Jahrhundert regiert der Stanforder Informatiker Donald Knuth als Geistführer des algorithmischen Reiches. Mit mehr als einer Million Exemplaren im Druck ist “The Art of Computer Programming” die Bibel seines Fachgebietes. Mehr dazu in der Artikel in New York Times