Bubble sort rainbow

Page by Murray Bourne, IntMath.com. Last updated: 07 September 2019.

Sorting data is a very common task in the world of computer science. One of the simplest algorithms for doing so is the bubble sort.

The basic algorithm for the bubble sort is as follows:

1. Compare the first 2 items in the list. If the first is bigger than the second, then swap them, otherwise leave them as is.
2. Now compare the 2nd and 3rd items. Once again, if the 2nd is bigger than the 3rd item, swap them.
3. Continue until the end of the list, and the largest number will be at the end. We won't need to check this again.
4. Make a second pass since they won't all be in order yet. Now the last 2 numbers are in the correct positions, so we don't need to check them.
5. Continue the process, comparing one less pair each time.
6. The final pass will check the first 2 numbers only.

The idea is the lowest value will "bubble up" to the top, the second highest value will bubble up to the second position, and so on.

The bubble sort is a common programming exercise for budding computer scientists. It's an interesting challenge to visualize the algorithm.

Number bubble sort example

Let's first start with a simple numbers example. We start with the numbers and our aim is to sort them.

Click the "next" button for a step-by-step explanation of the process.

Rainbow bubble sort example

Here is another visualization of bubble sort by Gabriele Corti.

We start with the colors presented in a random order, and then sort them by hue (red is smallest, followed by orange, yellow, green, blue, indigo and violet), finally giving us a rainbow.

Click the "sort" button to start the process.

(Works fine in good browsers like Chrome, Firefox, Opera. Performance not guaranteed in IE or Edge, or older Safari browsers.)

The math

The math behind the coding of the two bubble sort examples is quite straightforward. It involves:

1. Arrays of numbers
2. Value comparisons (using <, that is, "less than") between adjacent elements of the array

The code

When a swap of values is necessary, the code in each bubble sort example involves temporarily storing the current array value in a tmp variable, assigning the current array element as the next array element (since it's smaller), then assigning the next array element to the tmp value.

Two interesting aspects of the rainbow example are:

1. The swaps are all done at one go, then the colored columns are moved on a delay set up in the CSS expression:
   columns.style.transition = `all 0.2s ${duration / numberOfColumns * i}s ease-out`;
2. The swaps are achieved using CSS "order" as in this expression:
   matchingColumn.style.order = i - sortedColumns.length;

Credits

The concept, javascript and CSS for the rainbow example are by Gabriele Corti, source: CodePen.