Bubble Sort (Exchange sort)

The bubble sort algorithm is a very simple algorithm to understand and to implement. It works great on small lists but is very inefficient on large lists.

A bubble sort works by comparing adjacent items and exchanging them if they are out of order. The meaning of "out of order" depends on how you want the items sorted: smallest to largest, or largest to smallest.

For example, suppose we have this list of numbers that we want to order from smallest to largest: 

7  4  1  3  8  6  9  5  2
The final list should look like this: 
1  2  3  4  5  6  7  8  9
Using the bubble sort algorithm, we simply compare two items at a time, swapping them if the left one is larger than the right one. (We want them ordered from small to large). Starting with the first two items: 
7  4  1  3  8  6  9  5  2
^  ^
7 is larger than 4, so we swap them: 
4  7  1  3  8  6  9  5  2
^  ^
Next, we compare items 2 and 3 and find that 7 > 1 
4  7  1  3  8  6  9  5  2
   ^  ^
so we swap them: 
4  1  7  3  8  6  9  5  2
   ^  ^
You can see that 7 > 3 as well: 
4  1  7  3  8  6  9  5  2
      ^  ^
so we swap them: 
4  1  3  7  8  6  9  5  2
      ^  ^
Now, we compare items 4 and 5. 7 is not greater than 8, so we don't swap. 
4  1  3  7  8  6  9  5  2
         ^  ^
We simply move to the next two items, which are items 5 and 6: 
4  1  3  7  8  6  9  5  2
            ^  ^
8 > 6, so we swap: 
4  1  3  7  6  8  9  5  2
            ^  ^
Continuing in this way we will compare 8 and 9 (no swap), 9 and 5 (swap), and then 9 and 2 (swap). The list now looks like this: 
4  1  3  7  6  8  5  2  9
More importantly, after this pass through the list, the value 9 is now in its proper position. 


If we print out the list after each iteration of the outer loop we will see this (assume that
i is the outer loop variable):


This was the starting array:


7  4  1  3  8  6  9  5  2



And this is the array after each iteration of i:





4  1  3  7  6  8  5  2  9       i == 0
1  3  4  6  7  5  2  8  9       i == 1
1  3  4  6  5  2  7  8  9       i == 2
1  3  4  5  2  6  7  8  9       i == 3
1  3  4  2  5  6  7  8  9       i == 4
1  3  2  4  5  6  7  8  9       i == 5
1  2  3  4  5  6  7  8  9       i == 6
1  2  3  4  5  6  7  8  9       i == 7
1  2  3  4  5  6  7  8  9       i == 8



You'll notice that the list was actually sorted after the 7th (i == 6) iteration, so we have
a few unecessary iterations. You could add a little code to break out of the loop early, if
you detect that the list is sorted. All you have to do is keep track of how many swaps you
did for each iteration of the outer loop. If the number of swaps is 0, that means that all
of the items are in their proper position.


This very small optimization can have a dramatic impact on efficiency when the lists are
already sorted or almost sorted.