Sortieren auf zwei­dimensionalen Prozessor­feldern

LS3-Sort

 English version  aufwärts

Ein sehr einfaches und gut zu implementierendes Verfahren zum Sortieren auf einem zwei­dimensionalen Prozessorfeld ist das Verfahren LS3-Sort von Lang, Schimmler, Schmeck und Schröder [LSSS 85].

 

Verfahren

Der Algorithmus LS3-Sort beruht auf einem Merge-Verfahren, welches vier sortierte k/2kreuzk/2-Felder zu einem sortierten kkreuzk-Feld vereinigt. Sortier­richtung ist die Schlangen­linie. Als Grund­operationen werden die Operationen shuffle und oets benutzt.

shuffle

Ein professioneller Kartenspieler mischt einen Stoß Spielkarten, indem er die erste und die zweite Hälfte reiß­verschluss­artig ineinander gleiten lässt. Die englische Bezeichnung hierfür ist perfect shuffle oder kurz shuffle. Sie steht für folgende Permutation, hier dargestellt für n = 8 Elemente:

0 1 2 3 4 5 6 7
0 4 1 5 2 6 3 7

Auf Prozessor­feldern kann die Permutation shuffle durch ein "Dreieck" von Vertauschungen zwischen Nachbar­elementen hergestellt werden:

0 1 2 3 4 5 6 7
Doppelpfeil
DoppelpfeilDoppelpfeil
DoppelpfeilDoppelpfeilDoppelpfeil
0 4 1 5 2 6 3 7
oets

Die Operation oets steht für einen Schritt von Odd-even Transposition Sort. Bei einem Even-Schritt werden alle Elemente, die sich an geraden Positionen der Sortier­reihen­folge befinden, mit ihren rechten Nachbar­elementen verglichen und gegebenenfalls vertauscht, bei einem Odd-Schritt alle ungeraden Elemente. Odd- und Even-Schritte werden abwechselnd angewandt.

 

 

Prozedur ls3Merge(k)
Eingabe:kkreuzk-Feld, dessen vier k/2kreuzk/2-Teilfelder in Schlangen­linie sortiert sind
Ausgabe:Das in Schlangen­linie sortierte kkreuzk-Feld
Methode:
  1. shuffle in den Zeilen
  2. Sortieren der Doppelspalten (in Schlangen­linie)
  3. 2k oets-Schritte auf der Schlangen­linie

 

Die Korrektheit der Prozedur ls3Merge wird mithilfe des 0-1-Prinzips gezeigt.

Ausgangs­situation ist ein nur mit Nullen und Einsen belegtes Feld, dessen vier Teilfelder sortiert sind. In Bild 1a ist diese Situation dargestellt (Nullen sind weiß dargestellt, Einsen grau). Jedes der Teilfelder enthält eine gewisse Anzahl von vollen Zeilen (a, b, c bzw. d) sowie möglicherweise eine angefangene Zeile.

Nach der Operation shuffle in Schritt 1 ergibt sich Bild 1b. In jeder Doppelspalte befinden sich a + b + c + d Einsen aus den vollen Zeilen plus maximal vier weitere Einsen aus den angefangenen Zeilen.

Fall 1:  a + b + c + d gerade

Nach dem Sortieren der Doppelspalten in Schritt 2 ergibt sich Bild 1c. Die Einsen aus den vollen Zeilen ergeben (a+b+c+d)/2 volle Zeilen. Zusätzlich sind in jeder Doppelspalte maximal vier Einsen aus den angefangenen Zeilen. Diese bilden eine aus maximal zwei Zeilen bestehende unsortierte Zone.

Situation zu Anfang ... ... nach dem Shuffeln der Zeilen ... ... und nach dem Sortieren der Doppelspalten
(a) (b) (c)
Bild 1:  Beweis der Korrektheit der Prozedur ls3Merge

Fall 2:  a + b + c + d ungerade

Ist a + b + c + d ungerade, so bilden die Einsen aus den vollen Zeilen in jeder Doppelspalte eine Stufe (Bild 2). Wenn jetzt in einer Doppelspalte 0 und in einer anderen 4 Einsen aus den angefangenen Zeilen hinzukämen, so ergäbe sich eine aus drei Zeilen bestehende unsortierte Zone.

Einsen aus den vollen Zeilen, wenn a+b+c+d ungerade
Bild 2:  Einsen aus den vollen Zeilen, wenn a+b+c+d ungerade

Dies ist jedoch nur dann möglich, wenn alle angefangenen Zeilen auf derselben Seite anfangen (z.B. alle links oder alle rechts). Bei der Sortier­richtung in Schlangen­linien bedeutet dies aber, dass die Zahlen a, b, c, d alle gerade oder alle ungerade sind. Dann aber kann ihre Summe nicht ungerade sein.

Wenn a + b + c + d ungerade ist, kommen also in jeder Doppelspalte entweder mindestens eine Eins oder höchstens drei Einsen hinzu. Somit umfasst die unsortierte Zone auch in diesem Fall höchstens zwei Zeilen.

In Schritt 3 der Prozedur wird die aus maximal zwei Zeilen, d.h. aus maximal 2k Elementen bestehende unsortierte Zone schließlich sortiert. Hierfür genügen 2k oets-Schritte.

Durch rekursive Anwendung der Prozedur ls3Merge kann ein völlig unsortiertes Feld sortiert werden:

 

Algorithmus ls3Sort(n)
Eingabe:Unsortiertes nkreuzn-Feld
Ausgabe:Das sortierte nkreuzn-Feld
Methode:
  1. wenn n>1 dann
    1. wende ls3Sort(n/2) rekursiv auf die vier n/2kreuzn/2-Teilfelder an
    2. ls3Merge(n)

 

 

Analyse

Die Analyse der Prozedur ls3Merge(k) ergibt folgende Anzahl von Operationen:

Schritt 1: k/2
Schritt 2: 2k
Schritt 3: 2k
insgesamt: 4.5k

Der Algorithmus LS3-Sort benötigt T(n)  =  4.5(n + n/2 + n/4 + ... + 2) Operationen; es gilt somit

T(n) kleiner gleich9n

In [LSSS 85] wird gezeigt, dass sich die Zeit­komplexität von LS3-Sort noch auf 7n verringern lässt, indem u.a. die Doppelspalten schneller als in 2k Schritten sortiert werden.

 

Simulation

Das folgende Applet zeigt den Ablauf von LS3-Sort mit einem 32kreuz32-Feld von Nullen und Einsen. Zur besseren Anschau­lichkeit werden die Operationen sequentiell angezeigt, auch wenn sie auf einem nkreuzn-Prozessorfeld parallel ablaufen könnten.

 

(Java-Applet zur Simulation von LS3-Sort)

 

Zusammenfassung

Der vorgestellte Algorithmus LS3-Sort zum Sortieren eines nkreuzn-Feldes hat die gleiche asymptotische Zeit­komplexität wie der Algorithmus von Thompson-Kung [TK 77], nämlich O(n). Hinsichtlich der Konstanten ist er jedoch um einen Faktor von gut 2 schlechter. Die Qualität des Algorithmus liegt in seiner Einfachheit bei gleichzeitiger asymptotischer Optimalität.

 

Literatur

[LSSS 85]H.W. Lang, M. Schimmler, H. Schmeck, H. Schröder: Systolic Sorting on a Mesh-Connected Network. IEEE Transactions on Computers C-34, 7, 652-658 (1985)
[TK 77]C.D. Thompson, H.T. Kung: Sorting on a Mesh-Connected Parallel Computer. Communications of the ACM, 20, 4, 263-271 (1977)
[Lan 12]H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Das Verfahren LS3-Sort finden Sie auch in meinem Buch über Algorithmen.
Weiterevertikaler Abstand Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphen­algorithmen, Arithmetik, Codierung, Kryptografie.

[Weitere Informationen]

Buch  

 

 

Weiter mit:   [Sortierverfahren 4-way Mergesort]   oder   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 20.07.2001   Updated: 08.03.2013
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik