Home page

Versión española

Home of...

The Three Dimensional Bubble Sort Algorithm

Image produced by a sort

Art or science?

I discovered this curious but probably completely useless algorithm in the fall of 1999. I even sent off a note to Dr. Dobb's Journal about it, and was delightfully surprised when they wrote back some months later and suggested I do an article for them. I was too busy at the time, and the world lost an opportunity for an incremental increase in useless knowledge. I am presenting this now; my gift to the world and perhaps my only legacy. Who knows maybe some mathematician working away in some dusty office may find it a keystone to solving some obscure theory.

The Concept...

The idea is very simple. Start with a screen populated with coloured pixels, randomly distributed. The number of possible colours doesn't matter, but it makes a more interesting image in the end if fewer colours are used. Then we begin sorting the pixels according to the following algorithm:

LOOP
For a screen of dimensions W, H
Pick a pixel at random coordinates x, y where x = {0 thru W - 1)}, y = {0 thru (H - 2)}
If amount of red in pixel below (at x, y+1) is greater than red in current pixel, swap pixels
Pick another pixel at random coordinates x, y where x = {0 thru (W - 2)}, y = {0 thru (H - 2)}
If amount of green in pixel to the lower right (at x+1, y+1) is less than green in current pixel, swap pixels
Pick another pixel at random coordinates x, y where x = {1 thru (W - 1)}, y = {0 thru (H - 2)}
If amount of blue in pixel to the lower left (at x-1, y+1) is less than blue in current pixel, swap pixels

if(!done)goto LOOP

We continue looping like this millions of times, until an equilibrium becomes established in which colours are sorted into pools. The pixels of pure colour within the pools become immobile, and the only action that continues after that is some interplay along the interfaces of the colour pools.

As a generalized way of examining this phenomenon, imagine a given pixel with a determined amount of red, green, and blue. Depending on it's red content, it experiences a force moving it up or down the screen, and depending on the amount of each of the other two colours, it experiences forces moving it diagonally left and right. It's final resting position is the vector sum of these three forces, in relation to all the other pixels on the screen. This sorting algorithm can be taken to even higher dimensions, and can be applied to any combination of properties, not just the colours of pixels. However, in any scenario I can imagine, conventional sorting techniques are far simpler and faster. If you find some use for this algorithm beyond creating psychedelic images, please let me know and please at least credit me for the idea.

3DSort.exe for the PC - WinZipped (26.6 Kb) is my latest Windows' GDI version (16 Feb 2004), which does the sort on various surface shapes (square, round, torus, etc.) in < 2 minutes for an area 512 pixel squared, and just seconds for an area 256 pixels squared. Optimized in assembler, it probably doesn't get any faster than this - at least on a P4 - 2 ghz platform, anyhow. Here are some images produced by it: Circle.gif, Triangle.gif, Torus.gif.

Some more images...

  1. sort based on RGB,

  2. sort based on RGB,

  3. sort based on YcrCb,

  4. sort based on YCrCb.

...

Update May 2005

3DSortEx.exe for the PC - WinZipped (17.1 Kb) is my latest demo of a special effect. It illustrates a sort based on a special palette of 15 hues of each of the colours: Red, Green, Blue, Magenta, Cyan, and Yellow, for a total of 90 colours. It seems that since in any of the colours only a maximum of two of the three primaries red, green, or blue are used, it allows a complete sort to take place ie: at the end all pixels have found a stable location, not like in the above where pixels at the interfaces on some of the colour pools never find a stable position.

Not only do we get a stable sort, but if sorted on a circle, we end up with a smooth spectrum. The colours form pie shaped wedges around the circle forming a classic colour wheel running through the rainbow. In final analyses, however, how this could be of any use alludes me.

Since the human eye cannot distinguish among all the hues of each colour, I have added an old animation trick - palette animation - to demonstrate that indeed the colours have sorted in perfect spectral order. After doing a sort in the provided application 3DsortEX, hit "Toggle rotations" and you will see a colourful, rapidly rotating, "Beach ball". This is only possible because the colours have been sorted in spectral order around the circle. Each colour in the image is assigned a palette index, and by rotating the colours of the palette and re-applying them on each frame, it appears as if the whole image is rotating. Here is the code I wrote to create the colour palette.

...

Below is a graph that illustrates progress during the sort for various numbers of colours on a square 512 pixels on a side. It can take almost 200 million iterations to reach a steady state. My first versions years ago took over two hours to do the sort. Only with today's P4 processors and hand-optimized assembler code can the sort be now done in a couple of minutes instead of hours. It can be seen that number of colours doesn't make a lot of difference as to when the algorithm reaches a steady state, where the colours are sorted as much as they can be. The only dramatic difference is that with more colours, more pixels are left to forever wander along the interfaces without a home to call their own.

The colours were derived by stepping each red, green, and blue colour component by 128, 64, 32, 16, or 8, then removing the black, white, and grays from the resultant colours for purely aesthetic reasons. This yields 25, 123, 727, 4,911, and 35,935 colours respectively.

Graph of sort progress


-Back-

Valid HTML 4.0 Transitional