Hello! Today, we’ll be looking at bubble sort. Bubble sort is a sorting algorithm that behaves like “bubbles” and takes O(n²) time complexity. The key point of bubble sort is that “For each iteration, we drag the greatest element to the end(decrement by 1 each time) by each consecutive pair”. Let’s take an example.
- [5,3,1] -> [3,5,1] -> [3,1,5]
- [3,1,5] -> [1,3,5]
Notice that for each iteration, the last element is replaced by the greatest element. Therefore, decrement the searching range of the array by 1 for each iteration.
A slight optimization can be done. If nothing happens for an iteration, then it means the array is already sorted so pause it.
