Sortieren auf zweidimensionalen Prozessorfeldern

Das Verfahren 3n-Sort von Schnorr und Shamir [SchSh 86] ist komplizierter als etwa Rotatesort oder LS3-Sort. Mit einer Zeit­komplexität von 3n + O(n^3/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×n^3/4-Teilfeld, eine waagerechte Scheibe ist ein n^3/4×n-Teilfeld und ein Block ist ein n^3/4×n^3/4-Teilfeld (Bild 1).

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).

Im Algorithmus 3n-Sort wird ein n^1/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 n^1/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 n^3/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 ∈ {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.

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

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 n^1/4-fach-unshuffle verteilt jeweils die Spalten eines Blocks reihum auf alle n^1/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 n^1/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 n^1/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

Schritt 4

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

Ferner unter­scheiden sich die Gewichte von je zwei senkrechten Scheiben um höchstens n^1/4 · n^1/4  =  n^1/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 n^3/4 ein Gewichts­unterschied von n^1/2 höchstens eine zusätzliche volle 1-Zeile erzeugen kann.

Wir nennen den Bereich der Länge n^1/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).

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 n^1/4 · n^1/2  =  n^3/4 Elemente aus den kritischen Bereichen (Bild 3b / Bild 2f). Es verbleibt also eine unsortierte Zone der Länge höchstens n^3/4 auf der Schlangen­linie.

Schritt 7

In Schritt 7 wird die unsortierte Zone der Länge höchstens n^3/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:

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(n^3/4) sortieren, weil sie nur einen Bereich von n^1/4 gemischten Zeilen enthalten (z.B. durch Sortieren der Blöcke und anschließendes Sortieren der um n^1/4 Zeilen nach unten versetzten Blöcke).

Zusammenfassung

Der vorgestellte Algorithmus 3n-Sort von Schnorr-Shamir zum Sortieren eines n×n-Feldes hat eine Zeit­komplexität von 3n + O(n^3/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(n^2/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 Themen des Buches: Sortieren, Textsuche, Parsen und Übersetzen, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie.

[Weitere Informationen]