AW: Hilfe: Schnellste möglichkeit ein 4-Byte Array zu Sortieren
11. Feb 2012, 09:31
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.
Geändert von Furtbichler (11. Feb 2012 um 09:35 Uhr)
|