Bubble Sort Algorithm
All sorting algorithms take a list of data (numbers, letters) and sort it into either ascending order with smallest number first and biggest number last or descending order (biggest number first). Note lists are often called Arrays.
Bubble sort is the simplest of the sorting algorithms, it is the easiest to code but unfortunately it is also one of the slowest.
The way it works is it takes a list of numbers and compares each number to the one next to it, swapping them if needed, so the smallest one of the pair is first (assuming we are going ascending).
It then moves onto the next pair and does the same. When it gets to the end of the list (a pass), it goes back to the start and repeats the process. It keeps doing this until it has gone all through the list and not swapped anything.
Take a look at the example below and watch the video and it should make sense:
Example - Starting list : [ 4, 2, 6, 3, 9]
First pass:
- compares the first two elements (first pair) 4 and 2. It swaps them because 2 is less than(<) 4 >>>
[2, 4, 6, 3, 9] - compares second pair, 4 and 6. As 4 < 6, no swap needed >>>
[2, 4, 6, 3, 9] - Third pair - 6 and 3, swap because 3 < 6, so >>>
[2, 4, 3, 6, 9] - The last pair, 6 and 9, are already in order, so the algorithm does not swap them. [2, 4, 3, 6, 9]
,
Second pass through the list:
- First pair: 2 < 4, so there is no need to swap positions >>>
[2, 4, 3, 6, 9] - Second pair: swap because 3 < 4 , >>>
[2, 3, 4, 6, 9] - Third pair: No swap as 4 < 6, >>>
[2, 3, 4, 6, 9] - Again, 6 < 9, so no swap occurs, >>>
[2, 3, 4, 6, 9]
The list is sorted but the algorithm doesn't know that as it made a swap in this pass so there would be a third pass with no swaps - at the end of that swap the algorithm knows it has sorted the list.