Bubble Sort
The sorting algorithm works on the principle of moving the largest element to the end of the array just like a bubble moves up.
We do multiple pass over the array till its sorted, during each pass we compare the adjacent elements ( i.e i
and i+1
) and swap if the first is greater than the second. So at the end of the pass the largest element is at the top.
After each pass, the last part of the array will become sorted. That is why the last index of the range decreases by 1 after each pass.
This decrement is achieved by the outer loop and the last index is represented by variable i
in the above code.
The inner loop by j
helps to push the maximum element of range [0….i]
to the last index (i.e. i
)
If the array becomes sorted before all passes, to avoid unnecessary work we can have a small check to see if the array is already sorted
If the array is already sorted no swap will occur and we will break out from the loops.
Last updated