The Bubble Sort Algorithm
We apply this algorithm to sort a jumbled list into order. The list might be a list of numbers, letters, both or some other type. Each member of the list has a fixed place in a hierarchy compared to the others. If our list is a list of letters, the hierarchy would be alphabetical order. For illustrative simplicity our first example is a list of numbers and we sort them into numerical order.
18,16 ,4,6,8,1
We compare the first two to see which one is larger. 18 is larger than 16 so we swap them. The 18, being the larger, has to go after the 6, since we are sorting into numerical order.
16, 18,4 ,6,8,1
Then we compare the 18 and the 4. 18 is larger than 4 so we swap them.
16,4, 18,6 ,8,1
Then compare 18 with 6: since 18 is larger swap.
16,4,6, 18,8 ,1
Then 18 with 8 to get
16,4,6,8, 18,1
Then 18 with 1
16,4,6,8,1,18
It is called the bubble sort because the largest number rises to the end with each “pass”. We have just finished the first pass. We are now on the second pass. Compare the 16 and 4
4,16 ,6,8,1,18
and swap.
4, 16,6 ,8,1,18
Then 16 with 6
4,6, 16,8 ,1,18
Then 16 with 8
4,6,8, 16,1 ,18
Then 16 with 1
4,6,8,1,16,18
We have finished the second pass. There are six numbers in our list. On the first pass, we had to do 5 comparisons. In the second pass we did 4 comparisons. We are on the third pass. We start at the left hand side, by comparing 4 and 6, which are the right way round, so don't swap.
4,6 ,8,1,16,18
Compare 6 and 8, also the right way round, so don't swap.
4, 6,8 ,1,16,18
Compare 8 and 1. The 8 is bigger, so swap.
4,6, 1,8 ,16,18
The third pass is finished: it had 3 comparisons. We start the fourth pass, at the left hand side. Compare 4 and 6. No swap.
4, 6,1 ,8,16,18
Compare 6 and 1. Swap. In the fourth pass, 2 comparisons. We start the fifth pass.
4,1 ,6,8,16,18
Compare 4 and 1. Swap.
1,4,6,8,16,18
The bubble sort algorithm is finished. The list is in the right order. We did 5+4+3+2+1=15 comparisons altogether. In general for a list of
terms, we do
comparisons.