Sorting on two dimensional processor arrays

Random sort

 German version  up

Java has to be enabled to view this visualization

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

Code

The algorithm starts with an array of random colored pixels, drawn from 64 different colors.

Then some pixel is chosen at random. If its amount of red color is greater than the amount of red in its left neighbour pixel the two pixels are exchanged.

Again some pixel is chosen at random. If its amount of green color is greater than the amount of green in its lower right neighbour pixel the two pixels are exchanged.

And once again some pixel is chosen at random. If its amount of blue color is greater than the amount of blue in its upper right neighbour pixel the two pixels are exchanged.

This procedure is repeated for some million times.

 

Algorithm RandomSort
Input:An n × n-array of pixels with random color
Method:
  1. repeat
    1. choose a random pixel (i, j)

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

      1. exchange pixels (i, j) and (i, j-1)

      choose a random pixel (i, j)

      if green(i, j) > green(i+1, j+1)

      1. exchange pixels (i, j) and (i+1, j+1)

      choose a random pixel (i, j)

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

      1. exchange pixels (i, j) and (i-1, j+1)

 

 

Execution of this algorithm yields the first picture shown above. The other pictures are generated by a slight variation of the algorithm, adding some other exchanges with respect of certain colors. The last two pictures are generated using random parameters.

References

The algorithm is due to an idea of George W. Taylor, see

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

 

Next:  [Sequential and parallel sorting algorithms]   or   up

 

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