Sortiernetze

Transformationen von Sortiernetzen

 aufwärts

Wir betrachten Trans­formationen von Sortier­netzen. Gemeint sind Ver­änderungen an den Vergleichern des Netzes, die jedoch die Eigenschaft des Netzes, alle Eingabe­folgen zu sortieren, unberührt lassen.

Einschränkung von Sortiernetzen

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 Sortier­netzwerk für die restlichen n-1 Eingabe­linien.

Das Sortiernetz N7 hat die bemerkens­werte Eigenschaft, dass durch derartiges fort­gesetztes Streichen der untersten Eingabelinie zusammen mit den dort endenden Vergleichern sich optimale Sortiernetze für n = 6, ..., 2 ergeben.

Bild 1: Sortiernetz N7
Bild 1: Sortiernetz N7
Bild 2: Sortiernetz N6c
Bild 2: Sortiernetz N6c
Bild 3: Sortiernetz N5c
Bild 3: Sortiernetz N5c
Bild 4: Sortiernetz N4c
Bild 4: Sortiernetz N4c
Bild 5: Sortiernetz N3c
Bild 5: Sortiernetz N3c
Bild 6: Sortiernetz N2c
Bild 6: Sortiernetz N2c

Umordnen der Eingänge

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
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 Sortier­netzes durchlaufen, es wird die durch den jeweiligen Vergleicher bewirkte Veränderung der Permutation vorgenommen, und der möglicher­weise 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 8: Sortiernetz N8
Bild 8: Sortiernetz N8

 

Bild 9: N8 mit geshuffelten Eingängen,
Bild 9: N8 mit geshuffelten Eingängen,

 

Bild 10: N8 mit unshuffelten Eingängen
Bild 10: N8 mit unshuffelten Eingängen

 

Bild 11: N8 mit symmetrisch permutierten Eingängen
Bild 11: N8 mit symmetrisch permutierten Eingängen

Vertikales Spiegeln

Wird ein Sortiernetz (Bild 12 a) vertikal gespiegelt (Bild 12 b), so sortiert es offenbar in absteigender Richtung statt in auf­steigender Richtung. Werden anschließend die Richtungen aller Vergleicher umgekehrt (Bild 12 c), so sortiert es wieder in auf­steigender Richtung.

 

Bild 12: Vertikales Spiegeln eines Sortiernetzes
Bild 12: Vertikales Spiegeln eines Sortiernetzes

Durch eine ent­sprechende vertikale Spiegelung ergibt sich im allgemeinen ein anderes Sortiernetz. Ein Sortiernetz heißt symmetrisch, wenn es sich durch vertikale Spiegelung nicht ändert (abgesehen möglicher­weise von der irrelevanten Reihenfolge der Vergleicher innerhalb einer Vergleicher­stufe). Ein Beispiel für ein symmetrisches Sortiernetz ist das Sortiernetz N8.

 

Bild 13: Sortiernetz N8
Bild 13: Sortiernetz N8

 

Bild 14: N8 vertikal gespiegelt
Bild 14: N8 vertikal gespiegelt

 

Literatur

[BB 11]S.W. Al-Haj Baddar, K.E. Batcher: Designing Sorting Networks. Springer (2011)

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 14.12.2014   Updated: 04.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik