Bubble Sort
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. You should consider instead merge sort or quick sort in practice.
The Algorithm
- Compare the first two numbers and if the first number is greater than the second number, swap the numbers in the array.
- Move onto the next two numbers until the end of array (ignore locked elements).
- Lock the last element of the array.
- 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 6 3 7 5 2 8
- 1 3 6 5 2 7 |8|
- 1 3 5 2 6 |7||8|
- 1 3 2 5 |6||7||8|
- 1 2 3 |5||6||7||8|
- |1||2||3||5||6||7||8| (It is important to note that where there are no more swaps, the program terminates.)
