Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren

[Furtbichler]

Zur Information: Der 'Network sort' bedient sich dem minimalen Netzwerk, um 4 Elemente zu sortieren. Die Aufgabe ist nicht trivial, denn sie besteht darin die minimale Anzahl von Vergleichen bei gleichzeitig maximaler Parallelität zu ermitteln. Interessanterweise sind nur für N<=10 optimale Netzwerke bekannt.

Daraus ergibt sich dann ein Netzwerk (daher der Name), das aus N Leitungen sowie M Vergleichsbausteinen besteh. Ein Vergleichsbaustein hat jeweils 2 Ein- und Ausgänge. Wird der Eingang mit (A B) beschaltet und ist A>B, steht am Ausgang (B A) an.

Anwendung finden diese Netzwerke u.a. in GPU-Hardware.

Der Shellsort -mit den richtigen Gaps- liefert hier auch 5 Vergleiche und ein ähnliches Netzwerk.