Bubble Sort
Introduction
Suppose that we have a row of 8 stackable cups on a shelf arranged in a random order, and we wish to re-arrange them into order of size by placing the smallest cup on the left and then in increasing size up to the largest on the right.
By working from left to right we could compare each neighbouring cup to see if the left cup is smaller or larger than its neighbouring cup on the right. When the smallest is on the left we just move on a look at the next two cups, however if the larger cup is on the left we swap the left with the right cup so that now the left cup is the smaller sized cup and the right cup the larger sized. By repeating these comparisons and making swaps when necessary we eventually work to the end of the row.
At this point it is unlikely that all the cups are sorted in order, but it should be possible to see that the largest cup of all is now on the far right where we would expect it to be. You should also be able to see that the smallest cup has moved at least one position to the left (unless its already the left most cup). This is where the name bubble sort comes from because after each loop the smaller items bubble to the top (or left in our case) and the bigger items sink to the bottom (or right).
If we go back and start from the left and follow the same procedure again we end up with the both the second largest and largest cups on the right. Each time we repeat the procedure the next largest “unsorted” cup will end up in the expected “sorted” position on the right.
The simulation above shows how this works in practice. Every cycle (or loop) through the cups from left to right will guarantee that at least one more cup will fall into order on the right hand side. We may also observe that when we have 8 cups to sort, in the first cycle we do 7 checks or comparisons to check the relative order of the two neighbouring cups. We could continue to do all 7 checks through each cycle but this is unnecessary and inefficient as we know that the rightmost cup(s) in the previous cycle are now in order, so to save time and effort we do one less comparison(s) each cycle, until the final cycle where we only need to check the two leftmost cups to see if they are in order or not.
The number of comparisons needed in the first loop or cycle is always one less than the number of items that are being sorted. With 8 cups we need 7 comparisons, with 12 cups we would need 11 comparisons. We can even predict the total number of comparisons needed (but not the number of swaps) , for example for the 8 cups to be sorted in the above simulation we would need to do 28 comparisons 7+6+5+4+3+2+1. This is known as the Triangular Number series. We can even simplify the the calculation to n times n + n divided by 2, where n is one less than the number of cups (remember we are calculating the number of comparisons required).
So for 8 cups we need 7 x 7 + 7 all divided by 2 = 49 + 7 all divided by 2 so 56 divided by 2 = 28.
For 201 cups we would need 200 x 200 + 200 divided by 2 or 40200 divided by 2 or 20100 comparisons. As you can see the bubble sort is not very efficient, sorting 200 items is not very many (for a computer) but it requires over 20,000 comparisons to be made. While bubble sort is an example of a simple sorting algorithm that will produce the desired result its not that efficient. What we really need is a much more efficient method.
Exercise:
Think about the bubble sort algorithm above, and run the simulation a few times (F5 to refresh the screen to initiate another run sequence. Observe what happens when the cups are almost in order.
In your mind think of the cups starting off in the correct order:
Are the same number of comparisons made if the cups start off in the right order?
If there are no changes made in a particular cycle are there any more changes made in the remaining cycles?
How you could alter the algorithm to make use of what you have discovered?