Sortiernetze
Transformationen von Sortiernetzen
| 
|
Wir betrachten Transformationen von Sortiernetzen. Gemeint sind Veränderungen an den Vergleichern des Netzes, die jedoch die Eigenschaft des Netzes, alle Eingabefolgen zu sortieren, unberührt lassen.
Werden bei einem Standard-Sortiernetz 0-1-Folgen eingegeben, wobei jedoch die unterste Eingabelinie konstant mit 1 belegt wird, so bleiben alle Vergleicher, die auf der untersten Eingabelinie enden, untätig, d.h. sie führen keine Vertauschung durch. Indem die unterste Eingabelinie zusammen mit den dort endenden Vergleichern entfernt wird, ergibt sich ein Sortiernetzwerk für die restlichen n-1 Eingabelinien.
Das Sortiernetz N7 hat die bemerkenswerte Eigenschaft, dass durch derartiges fortgesetztes Streichen der untersten Eingabelinie zusammen mit den dort endenden Vergleichern sich optimale Sortiernetze für n = 6, ..., 2 ergeben.
Ein Sortiernetz sortiert jede beliebige Permutation der Eingabedaten. Daher sortiert das Sortiernetz nach wie vor, wenn seine Eingänge permutiert werden, auch wenn die Ausgänge nicht entsprechend permutiert werden. Allerdings ändern sich einige Vergleicher entsprechend [BB 11].
Als einfachstes Beispiel betrachten wir das Sortiernetz N3 (Bild 7 a) und vertauschen seine Eingänge 1 und 2 (Bild 7 b). Wir geben die sortierte Folge 0 1 2 ein. Wegen der Permutation der Eingänge entsteht hieraus die Folge 0 2 1. Damit der erste Vergleicher weiterhin die 0 und die 1 vergleicht, wird er in [0:2] geändert. Der zweite Vergleicher wird nicht geändert, denn er vergleicht nach wie vor 2 und 1. Der dritte Vergleicher wird auch nicht geändert, denn er vergleicht nach wie vor 0 und 1. Das geänderte Sortiernetz ist in Bild 7 c dargestellt.
|
|
| Bild 7: Sortiernetz N3 mit umgeordneten Eingängen |
|
Die folgende Methode erzeugt aus einem Sortiernetz ein neues Sortiernetz mit geänderten Vergleichern, entsprechend einer Permutation p der Eingänge. Mit einem Iterator werden die Vergleicher des Sortiernetzes durchlaufen, es wird die durch den jeweiligen Vergleicher bewirkte Veränderung der Permutation vorgenommen, und der möglicherweise geänderte Vergleicher wird an das neu zu erzeugende geänderte Sortiernetz angehängt.
public ComparatorNet relabelled(int[] p)
{
ComparatorNet cn=new ComparatorNet(size);
Iterator<Comparator> it=iterator();
Comparator c;
int i, j;
while (it.hasNext())
{
c=it.next();
i=Math.min(p[c.i], p[c.j]);
j=Math.max(p[c.i], p[c.j]);
p[c.i]=i;
p[c.j]=j;
cn.add(i, j);
}
return cn;
}
|
Die folgenden Abbildungen zeigen das Sortiernetz N8, dessen Eingänge mit den Permutationen shuffle, unshuffle und symmetric permutiert sind.
|
|
| Bild 9: N8 mit geshuffelten Eingängen, |
|
|
|
| Bild 10: N8 mit unshuffelten Eingängen |
|
|
|
| Bild 11: N8 mit symmetrisch permutierten Eingängen |
|
Wird ein Sortiernetz (Bild 12 a) vertikal gespiegelt (Bild 12 b), so sortiert es offenbar in absteigender Richtung statt in aufsteigender Richtung. Werden anschließend die Richtungen aller Vergleicher umgekehrt (Bild 12 c), so sortiert es wieder in aufsteigender Richtung.
|
|
| Bild 12: Vertikales Spiegeln eines Sortiernetzes |
|
Durch eine entsprechende vertikale Spiegelung ergibt sich im Allgemeinen ein anderes Sortiernetz. Ein Sortiernetz heißt symmetrisch, wenn es sich durch vertikale Spiegelung nicht ändert (abgesehen möglicherweise von der irrelevanten Reihenfolge der Vergleicher innerhalb einer Vergleicherstufe). Ein Beispiel für ein symmetrisches Sortiernetz ist das Sortiernetz N8.
|
|
| Bild 14: N8 vertikal gespiegelt |
|
| | |
| [BB 11] | S.W. Al-Haj Baddar, K.E. Batcher: Designing Sorting Networks. Springer (2011) |
Weiter mit:
 |
H.W. Lang Hochschule Flensburg lang@hs-flensburg.de Impressum Datenschutz © Created: 14.12.2014 Updated: 04.06.2018
