Ungerade-Gerade-Vertauschungs-Sortierung

Bei der Aktivität „Das weltgrößte Sortiernetzwerk” wird ein Sortiernetzwerk benutzt, das im berühmten Buch „The Art of Computer Programming” von Donald Knuth, erwähnt wird. Knuth nannte dieses Netzwerk „Ungerade-Gerade-Vertauschungs-Sortierung”. Dort gibt er 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 […]

Optimierung des Zeichnungsprozesses

Das Sortier-Netzwerk und seine Knoten müssen auf dem Boden dargestellt werden – kein trivialer Prozess. Die Schülerinnen und Schüler haben in Zusammenarbeit mit ihrem Informatiklehrer, Hermann Morgenbesser, und Prof. Stefan Szeider einen Probelauf zur Optimierung des Prozesses durchgeführt.

Netzwerk mit 2500 Knoten

Die 50 Eingabeknoten erfordern 50 TeilnehmerInnen, um den Sortieralgorithmus auf dem Feld mit 2500 Knoten durchzuführen. Zwei Knoten sind durch einen Punkt repräsentiert. Ein Sortiernetzwerk hat drei Arten von Knoten: Eingangsknoten, an denen die unsortierten Daten anliegen, Vergleichsknoten, an denen Daten paarweise verglichen werden, und Ausgangsknoten, wo am Ende die sortierten Daten anliegen. Im menschlichen […]

Wie wird sortiert?

Dies ist ein Beispiel für ein Sortier-Netzwerk mit 8 Eingangsknoten. Der verwendete Sortieralgorithmus ist die Odd-Even Sort. Die Grafik wurde von Prof. Stefan Szeider entworfen. Eine ähnliche Grafik wird für das T-Shirt-Motiv verwendet.