Bubble Sort is the simplest sorting algorithm that repeatedly scrolls through the list, compares adjacent elements and swaps them if they are in the wrong order. This sort is not used in real-world project because is very performs poorly.
We start with an array, not sorted, composed like this:
[8,5,2,6,12] The algorithm consists in cycling the array, checking if each element is ordered with respect to its next, and if necessary swap them, all this until by cycling the whole array 0 exchanges are obtained. In our example:
- Check if the first item is sorted with the next element (8,5)
- Swap the two value e pass to the next index (5,8)
- Check if the second element is sorted with the next element (8,2)
- Swap the two value e pass to the next index (2,8)
- Check if the third item is sorted with the next element (8,6)
- Swap the two value e pass to the next index (6,8)
- Check if the third item is sorted with the next element (8,12)
- In this case don’t swap the elements (8,12)
- Start over.
The original algorithm does not include the
swapped flag, but this has the disadvantage, that regardless of whether the array is already sorted or not, we would have to loop it n² times (one complete loop for each main loop). The flag certainly helps in cases where the array is already ordered or in any case it is partially ordered, but in any case the complexity of the algorithm in the worst cases remains at all.