An introduction to an algorithm for bubble sorting
Bubble sorting is a method of sorting data. The idea is that you make multiple passes through data. A pass through the data consists of making a set of comparisons between two data items. You always start with the items in position 0 and 1, then 1 and 2, then 2 and 3 etc and each time, you compare them and swap them if necessary. After you have made a pass through all of the data, the biggest piece of data will be in the correct place. It has 'bubbled up' to the surface, so to speak, which is where this algorithm gets it name from.
You then make another pass through all of the data as before, except this time, there will be one less comparison to make as the data on the right will be in the correct position. In fact, after each pass, you will always put one more piece of data into the right place and need to do one less comparison the next time! You can see how this works in the animation from Wikipedia on the left.
Here is the first complete pass through the data 6, 5, 3, 1, 8, 7, 2, 4
6 | 5 | 3 | 1 | 8 | 7 | 2 | 4 | Original data |
5 | 6 | 3 | 1 | 8 | 7 | 2 | 4 | Swap 6 and 5 |
5 | 3 | 6 | 1 | 8 | 7 | 2 | 4 | Swap 6 and 3 |
5 | 3 | 1 | 6 | 8 | 7 | 2 | 4 | Swap 6 and 1 |
5 | 3 | 1 | 6 | 8 | 7 | 2 | 4 | Don't swap |
5 | 3 | 1 | 6 | 7 | 8 | 2 | 4 | Swap 8 and 7 |
5 | 3 | 1 | 6 | 7 | 2 | 8 | 4 | Swap 8 and 2 |
5 | 3 | 1 | 6 | 7 | 2 | 4 | 8 | Swap 8 and 4 |
Note the following:
1. You can see that as soon as you find the biggest value, that will always be part of the pair of comparisons you do in that pass.
2. The value 8 is now in the correct position.
3. We started with 8 pieces of data, and had to do 7 comparisons in the first pass.
4. After one pass, the biggest piece of data is in the correct position.
5. If we had n pieces of data, we would need to make n-1 comparisons in the first pass.
6. Next time, for the second pass, we only have to do 6 comparisons.
7. After two passes, the two biggest pieces of data are in the correct position.
8. If we had n pieces of data, we would need to make n-2 comparisons in the second pass.
9. In the second pass. we will start with the first two pieces of data as before, but just do one less comparison at the end.
10. Next time, for the third pass, we only have to do 5 comparisons.
11. After three passes, the three biggest pieces of data are in the correct position.
12. If we had n pieces of data, we would need to make n-3 comparisons in the third pass.
13. In the third pass. we will start with the first two pieces of data as before, but just do two less comparisons at the end.
Bubble sorts are quite slow compared to insertion sorts. If you remember, we have already said that the efficiency of a sorting algorithm is related to how many comparisons you have to do. The more you have to do, the longer your program code takes to run. You usually have to do a lot more comparisons in bubble sorting than insertion sorting.