Sortieren auf zweidimensionalen Prozessorfeldern

Random sort

 English version  aufwärts

Java has to be enabled to view this sorting contest

(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:
  1. Wiederhole
    1. wähle einen zufälligen Bildpunkt (i, j)

      wenn red(i, j) > red(i, j-1)

      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)

      1. vertausche Bildpunkte (i, j) und (i+1, j+1)
    1. wähle einen zufälligen Bildpunkt (i, j)

      wenn blue(i, j) > blue(i-1, j+1)

      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   up

 

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


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