Sortieren auf zweidimensionalen Prozessorfeldern

Algorithmus 4-Way-Mergesort

 English version  aufwärts

Ein besonders einfaches und gut zu implementierendes Verfahren ist das Verfahren 4-way-Mergesort von Schimmler [Schi 87].

Verfahren

Definition:  Ein m×n-Feld von Daten heißt grobsortiert, wenn jedes Element bereits in der richtigen Zeile steht (so dass also anschließendes Sortieren der Zeilen ausreicht, um das Feld vollständig zu sortieren).

Der Algorithmus 4-way-Mergesort beruht auf einem Merge-Verfahren, welches vier grob­sortierte k/2×k/2-Felder zu einem grob­sortierten k×k-Feld vereinigt.

 

Prozedur 4-way-merge(k)
Eingabe:k×k-Feld, dessen vier k/2×k/2-Felder grobsortiert sind
Ausgabe:Das grobsortierte k×k-Feld
Methode:
  1. Sortieren der Zeilen der Teilfelder:
    1. aufsteigend in den oberen Teilfeldern,

      absteigend in den unteren Teilfeldern;

  2. Sortieren der Spalten;
  3. Sortieren der Zeilen:
    1. ungerade Zeilen aufsteigend,

      gerade Zeilen absteigend;

  4. Sortieren der Spalten;

 

Die Korrektheit der Prozedur 4-way-merge kann in sehr anschau­licher Weise mithilfe des 0-1-Prinzips gezeigt werden. (Das 0-1-Prinzip gilt auch für den Begriff "grobsortiert", da durch anschließendes Sortieren der Zeilen der sortierte Zustand herbei­geführt werden kann.)

Ausgangs­situation ist ein nur mit Nullen und Einsen belegtes Feld, dessen vier Teilfelder grobsortiert sind. In Bild 1a ist diese Situation dargestellt (Nullen sind weiß dargestellt, Einsen grau).

Nach dem Sortieren der Zeilen der Teilfelder in Schritt 1 ergibt sich Bild 1b.

Nach dem Sortieren der Spalten in Schritt 2 ergeben sich zwei grob­sortierte k×k/2-Felder (Bild 1c).

Nach dem gegenläufigen Sortieren der Zeilen in Schritt 3 sind zwei unterschiedliche Situationen möglich: entweder befinden sich die "gemischten" Halbzeilen (d.h. Halbzeilen in denen sowohl Nullen als auch Einsen vorkommen) aus Bild 1c in ver­schiedenen Hälften (Bild 1d) oder in der gleichen Hälfte des Feldes (in Bild 1e in der rechten Hälfte). Dies hängt von der Anzahl der vollständig mit Einsen belegten Halbzeilen ab.

In beiden Fällen jedoch führt das Sortieren der Spalten in Schritt 4 zu der in Bild 1f gezeigten Situation, nämlich einem grob­sortierten k×k-Feld.

Bild 1: Beweis der Korrektheit der Prozedur 4-way-merge mit Hilfe des 0-1-Prinzips
Bild 1: Beweis der Korrektheit der Prozedur 4-way-merge mit Hilfe des 0-1-Prinzips

Durch rekursive Anwendung der Prozedur 4-way-merge kann ein völlig unsortiertes Feld grobsortiert werden:

 

Prozedur roughsort(k)
Eingabe:Unsortiertes k×k-Feld
Ausgabe:Das grobsortierte k×k-Feld
Methode:
  1. wenn k>1 dann
    1. roughsort(k/2) auf die vier k/2×k/2-Teilfelder anwenden;

      4-way-merge(k);

 

Ein n×n-Feld wird sortiert, indem es zunächst grobsortiert wird und dann die Zeilen sortiert werden:

 

Algorithmus 4-way-Mergesort(n)
Eingabe:Unsortiertes n×n-Feld
Ausgabe:Das sortierte n×n-Feld
Methode:
  1. roughsort(n);
  2. Zeilen sortieren;

 

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 der Prozedur 4-way-merge ergibt folgendes, wenn das Sortieren einer Zeile bzw. Spalte der Länge k mit Odd-even Trans­position Sort k Schritte dauert:

Schritt 1: k/2 Schritte
Schritt 2: k Schritte
Schritt 3: k Schritte
Schritt 4: k/2 Schritte
insgesamt: 3k Schritte

In Schritt 4 sind nur k/2 Schritte von Odd-even Trans­position Sort erforderlich, da jede Spalte aus zwei ineinander ver­schränkten sortierten Teilfolgen besteht.

Der Algorithmus 4-way-Mergesort benötigt für die rekursive Ausführung von 4-way-merge im Aufruf von roughsort insgesamt 3n + 3n/2 + 3n/4 + ... + 3 kleiner gleich 6n Schritte. Für das anschließende Sortieren der Zeilen sind noch einmal n Schritte erforderlich, so dass sich insgesamt ergibt:

T(n) kleiner gleich7n

Simulation

Das folgende Applet zeigt den Ablauf von 4-way-Mergesort mit einem 32×32-Feld von Nullen und Einsen. Zur besseren Anschaulich­keit werden die Operationen sequentiell angezeigt, auch wenn sie auf einem zwei­dimensionalen Prozessor­feld parallel ablaufen könnten.

 

(Java-Applet zur Simulation von 4-way-Mergesort)

Zusammenfassung

Der vorgestellte Algorithmus 4-way-Mergesort zum Sortieren eines n×n-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 gleich­zeitiger asymptotischer Optimalität.

Eine Implementierung des Algorithmus auf einem befehls­systolischen Feld ist in [Schi 87] sowie in [Lan 90] angegeben.

Literatur

[Lan 90]H.W. Lang: Das befehlssystolische Prozessorfeld -- Architektur und Programmierung. Dissertation, Christian-Albrechts-Universität Kiel (1990)
[Schi 87]M. Schimmler: Fast Sorting on the Instruction Systolic Array. Bericht Nr. 8709, Institut für Informatik, Christian-Albrechts-Universität Kiel (1987)
[TK 77]C.D. Thompson, H.T. Kung: Sorting on a Mesh-Connected Parallel Computer. Communications of the ACM, 20, 4, 263-271 (1977)

 

Weiter mit:   [Sortierverfahren Rotatesort]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 01.03.2000   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