Sortieren auf zweidimensionalen Prozessorfeldern

3n-Sort

 English version  aufwärts

Das Verfahren 3n-Sort von Schnorr und Shamir [SchSh 86] ist komplizierter als etwa Rotatesort oder LS3-Sort. Mit einer Komplexität von 3n + O(n3/4) ist es jedoch optimal, denn 3n ist eine untere Schranke für das Sortieren auf einem zwei­dimensionalen Prozessor­feld.

Verfahren

Das n×n-Feld wird in senkrechte Scheiben, waagerechte Scheiben und Blöcke unterteilt. Eine senkrechte Scheibe ist ein n×n3/4-Teilfeld, eine waagerechte Scheibe ist ein n3/4×n-Teilfeld und ein Block ist ein n3/4×n3/4-Teilfeld (Bild 1).

senkrechte Scheiben waagerechte Scheiben Blöcke
(a) (b) (c)
Bild 1: Senkrechte Scheiben (a), waagerechte Scheiben (b) und Blöcke (c)

Das gesamte Feld wie auch Teilfelder (Blöcke, Scheiben) werden stets in Schlangen­linie sortiert.

Der Algorithmus von Schnorr-Shamir verwendet folgende Operation unshuffle sowie die Operation oets (Schritt von Odd-even Trans­position Sort.

unshuffle

Eine k-fach-unshuffle-Operation ist eine Permutation, die dem Austeilen von n Karten an k Spieler entspricht (k ist Teiler von n).

Beispiel:  Permutation 4-fach-unshuffle der Zahlen 0, ..., 11

 0 1 2  3 4 5  6 7 8  91011
 0 4 8  1 5 9  2 610  3 711

Spieler 1 erhält die Karten 0, 4 und 8, Spieler 2 die Karten 1, 5 und 9 usw.

Im Algorithmus 3n-Sort wird ein n1/4-fach-unshuffle der Elemente der Zeilen durchgeführt.

 

Algorithmus 3n-Sort
Eingabe:Unsortiertes n×n-Feld von Daten
Ausgabe:Das sortierte n×n-Feld
Methode:
  1. sortiere die Blöcke
  2. wende n1/4-fach-unshuffle entlang der Zeilen an
  3. sortiere die Blöcke
  4. sortiere die Spalten
  5. sortiere die senkrechten Scheiben
  6. sortiere die Zeilen in gegenläufige Richtung
  7. wende n3/4 oets-Schritte auf der Schlangenlinie an

 

Gegen­läufiges Sortieren bedeutet, dass jede Zeile i aufsteigend sortiert wird, wenn i gerade ist, und absteigend, wenn i ungerade ist (i Element {0, ..., n-1}).

Korrektheit

Die Korrektheit von 3n-Sort wird wiederum mit Hilfe des 0-1-Prinzips gezeigt. In den folgenden Abbildungen sind Nullen weiß und Einsen grau dargestellt.

Definition:  Eine Zeile heißt einfarbig, wenn sie nur aus Nullen oder nur aus Einsen besteht, anderenfalls heißt sie gemischt. Eine gemischte Zeile in einem sortierten Feld heißt angefangene Zeile.

Definition:  Das Gewicht eines r × s-Teilfeldes ist gleich der Anzahl der Einsen in diesem Teilfeld.

Insbesondere bezieht sich diese Definition hier auf Spalten und auf Blöcke.

Definition:  Ein maximaler zusammen­hängender Bereich in der Sortier­reihen­folge, der mit einer Eins beginnt und mit einer Null endet, heißt unsortierte Zone.

Eine 0-1-Folge mit einer unsortierten Zone beginnt mit Nullen, dann kommt ein Gemisch von Einsen und Nullen, und dann kommen Einsen.

Schritt 1

Nach dem Sortieren der Blöcke enthält jeder Block höchstens eine angefangene Zeile (Bild 2a).

Schritt 2

Die Operation n1/4-fach-unshuffle verteilt jeweils die Spalten eines Blocks reihum auf alle n1/4 Blöcke derselben horizontalen Scheibe. Wenn der Block eine angefangene Zeile enthält, erhalten einige Blöcke jeweils eine Eins mehr als andere. Insgesamt kann dadurch ein Block höchstens n1/4 Einsen mehr als ein anderer erhalten, d.h. die Gewichte von je zwei Blöcken in der horizontalen Scheibe unter­scheiden sich höchstens um n1/4 (Bild 2b).

Schritt 3

Nach dem erneuten Sortieren der Blöcke enthält jeder Block höchstens eine angefangene Zeile (Bild 2c).

Bild 2: Situationen während der Ausführung des Algorithmus
Bild 2: Situationen während der Ausführung des Algorithmus
Schritt 4

Nach dem Sortieren der Spalten enthält jede senkrechte Scheibe höchstens n1/4 gemischte Zeilen (die angefangenen Zeilen ihrer n1/4 Blöcke).

Ferner unter­scheiden sich die Gewichte von je zwei senkrechten Scheiben um höchstens n1/4 · n1/4  =  n1/2 (Bild 2d).

Schritt 5

Nach dem Sortieren der senkrechten Scheiben haben alle senkrechten Scheiben fast gleich viele 1-Zeilen: der Unterschied beträgt höchstens 1. Dies liegt daran, dass aufgrund der Breite der senkrechten Scheibe von n3/4 ein Gewichts­unterschied von n1/2 höchstens eine zusätzliche volle 1-Zeile erzeugen kann.

Wir nennen den Bereich der Länge n1/2 auf der Schlangen­linie, innerhalb dessen eine senkrechte Scheibe zusätzliche Einsen gegenüber einer anderen senkrechten Scheibe enthalten kann, den kritischen Bereich (umrahmt dargestellt in Bild 3a).

kritische Bereiche vor Schritt 6 kritische Bereiche nach Schritt 6
(a) (b)
Bild 3: Kritische Bereiche in den senkrechten Scheiben: (a) vor Schritt 6 und (b) nach Schritt 6

Das gesamte Feld enthält insgesamt nur noch höchstens 2 gemischte Zeilen (Bild 2e).

Schritt 6

In Schritt 6 werden die beiden verbliebenen gemischten Zeilen gegenläufig sortiert. Möglicher­weise noch nicht fertig sortiert sind jetzt nur noch die höchstens n1/4 · n1/2  =  n3/4 Elemente aus den kritischen Bereichen (Bild 3b / Bild 2f). Es verbleibt also eine unsortierte Zone der Länge höchstens n3/4 auf der Schlangen­linie.

Schritt 7

In Schritt 7 wird die unsortierte Zone der Länge höchstens n3/4 entlang der Schlangen­linie fertig sortiert.

 

Dem 0-1-Prinzip zufolge sortiert das Verfahren jeden beliebigen Datensatz, da es nach obiger Argumentation alle 0-1-Datensätze sortiert.

Analyse

Die Analyse des Algorithmus ergibt folgendes:

Schritt 1: Sortieren der Blöcke O(n3/4)
Schritt 2: unshuffle entlang der Zeilen n
Schritt 3: Sortieren der Blöcke O(n3/4)
Schritt 4: Sortieren der Spalten n
Schritt 5: Sortieren der senkrechten Scheiben O(n3/4)
Schritt 6: Zeilen gegenläufig sortieren n
Schritt 7: n3/4 oets-Schritte O(n3/4) 
insgesamt:  3n + O(n3/4)

Das Sortieren der Blöcke kann mit irgendeinem linearen Sortier­verfahren durchgeführt werden, z.B. mit LS3-Sort.

Die senkrechten Scheiben lassen sich in Schritt 5 in O(n3/4) sortieren, weil sie nur einen Bereich von n1/4 gemischten Zeilen enthalten (z.B. durch Sortieren der Blöcke und anschließendes Sortieren der um n1/4 Zeilen nach unten versetzten Blöcke).

Simulation

Die folgende Simulation zeigt den Ablauf des Algorithmus von Schnorr-Shamir mit einem 256×256-Feld von Nullen und Einsen. Zur besseren Anschaulich­keit werden einige Operationen sequentiell angezeigt, auch wenn sie auf einem zwei­dimensionalen Prozessor­feld parallel ablaufen könnten.

 

(Java-Applet zur Simulation des Algorithmus von Schnorr-Shamir)

Zusammenfassung

Der vorgestellte Algorithmus 3n-Sort von Schnorr-Shamir zum Sortieren eines n×n-Feldes hat eine Zeit­komplexität von 3n + O(n3/4). Es ist daher sowohl asymptotisch optimal als auch hinsichtlich der Konstanten, denn 3n ist eine untere Schranke für das Sortieren auf einem n×n-Feld. Der Algorithmus von Schnorr-Shamir ist einfacher als der Algorithmus von Thompson-Kung [TK 77], der mit einer Zeit­komplexität von 3n + O(n2/3·log(n)) ebenfalls optimal ist.

Literatur

[SchSh 86]C.P. Schnorr, A. Shamir: An Optimal Sorting Algorithm for Mesh-Connected Computers. Proc. of the 18th ACM Symposium on Theory of Computing, 255-261 (1986)
[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 3n-Sort finden Sie auch in meinem Buch über Algorithmen.
Weitere(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie.

[Weitere Informationen]

Buch  

 

Weiter mit:   [Sortierverfahren von Thompson-Kung]   oder   up

 

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

Hochschule Flensburg
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