Bubble Sort

Bubble Sort Algorithm in motion

Understanding Bubble Sort

Bubble sort is a way of sorting an array of items. Bubble Sort is fairly simple to grasp as it is almost like bubbles rising up from a bottom of a fizzy drink - bigger bubbles on top, smaller on the bottom. It is also important to note that this is far from the most desirable algorithm to use in practice as it is really slow<ref>Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging. "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!" (Quote from the first edition, 1973.)</ref>. You should consider instead merge sort or quick sort in practice.

The Algorithm

1. Compare the first two numbers and if the first number is greater than the second number, swap the numbers in the array.
2. Move onto the next two numbers until the end of array (ignore locked elements).
3. Lock the last element of the array.
4. Repeat 1-3 until steps 1-3 have made no more swaps.

Worked Example

Imagine you have an array of numbers that need sorting:
 1  6  3  7  5  2  8  
You would start by comparing the first two items of the array:
[1][6] 3  7  5  2  8 
Due to the fact that, 6 > 1 therefore 1 stays in the same place. Move onto the next two elements:
 1 [6][3] 7  5  2  8 
We swap 6 and 3 because 3 < 6, then move onto the next two elements:
 1  3 [6][7] 5  2  8 
Because 6 is less than 7 we don't swap the numbers again then move on:
 1  3  6 [7][5] 2  8 
Again, because 7 is greater than 5, the number swap:
 1  3  6  5 [7][2] 8 
Once again, because 7 is greater than 2, you swap the numbers:
 1  3  6  5  2 [7][8] 
Because 8 is bigger than 7, the numbers don't swap:
 1  3  6  5  2  7 |8| 
The number 8 is now locked in as it is sure that this number is in the correct place in the array. At the end of each pass you lock the last number, reducing the array. The passes from the beginning would look like this:

1.  1  6  3  7  5  2  8  
2.  1  3  6  5  2  7 |8| 
3.  1  3  5  2  6 |7||8| 
4.  1  3  2  5 |6||7||8| 
5.  1  2  3 |5||6||7||8| 
6. |1||2||3||5||6||7||8|  (It is important to note that where there are no more swaps, the program terminates.)

Notes

<references/>