Sortieren auf zweidimensionalen Prozessorfeldern Random sort

Java has to be enabled to view this visualization (use Internet Explorer)

(Applet) (Applet) (Applet) (Applet) (Applet) (Applet) (Applet) (Applet) (Applet) (Applet)

Code

Das Verfahren beginnt mit einem Feld von Bildpunkten mit zufällig gewählter Farbe. Es werden 64 verschiedene Farben verwendet.

Dann wird zufällig ein Bildpunkt heraus­gegriffen. Wenn der Anteil der Farbe Rot in diesem Bildpunkt größer ist als im linken Nachbar­bildpunkt, werden die Bildpunkte vertauscht.

Anschließend wird zufällig ein weiterer Bildpunkt heraus­gegriffen. Wenn der Anteil der Farbe Grün in diesem Bildpunkt größer ist als im rechten unteren Nachbar­bildpunkt, werden die Bildpunkte vertauscht.

Und schließlich wird zufällig noch ein Bildpunkt heraus­gegriffen Wenn der Anteil der Farbe Blau in diesem Bildpunkt größer ist als im rechten oberen Nachbar­bildpunkt, werden die Bildpunkte vertauscht.

Das ganze wird ein paar Millionen mal wiederholt.

 

Algorithmus RandomSort
Eingabe:	Ein n × n-Feld von Bildpunkten mit zufällig gewählter Farbe
Methode:	Wiederhole wähle einen zufälligen Bildpunkt (i, j) wenn red(i, j) > red(i, j-1) vertausche Bildpunkte (i, j) und (i, j-1) wähle einen zufälligen Bildpunkt (i, j) wenn green(i, j) > green(i+1, j+1) vertausche Bildpunkte (i, j) und (i+1, j+1) wähle einen zufälligen Bildpunkt (i, j) wenn blue(i, j) > blue(i-1, j+1) vertausche Bildpunkte (i, j) und (i-1, j+1)

 

 

Bei Anwendung dieses Verfahrens ergibt sich das erste der oben dar­gestellten Bilder. Durch Variation des Verfahrens, indem weitere Ver­tauschungen mit bestimmten Nachbar­bildpunkten bezüglich bestimmter Farbanteile vorgenommen werden, ergeben sich die weiteren Bilder. Bei den letzten beiden Bildern werden zufällig gewählte Parameter verwendet.

Literatur

Das Verfahren geht auf eine Idee von George W. Taylor zurück, siehe

[Web 1]	http://www.tropicalcoder.com/3dBubbleSort.htm

 

Weiter:  [Sequentielle und parallele Sortierverfahren]   oder

 

H.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 31.01.2011   Updated: 20.08.2018