Bubble Sort
#
Overview- Time Complexity: Best -
O(n)
, Worst -O(n^2)
- Space Complexity:
O(1)
- In-Place
- Stable
#
General IdeaThink of bubbling each element across the array. Starting from the first element we compare it with the neighbouring element. If the current element is larger than the neighbouring element, we swap the positions. Now we increase the positions of both pointers by one and repeat the same.
At the end of the first iteration the largest element in the array is placed at the last index in the array.
#
Time ComplexityAs we can see, there are 2 loops. An outer loop which goes through the entire array and an inner loop which traverses from the current to the (arr.length - i - 1)
index. This is because we do not need to consider the last i
elements which have already been populated with the top i
largest elements.
This yields a time complexity of O(n^2)
.
To optimise this, we can have a flag to check if any swaps have been made in the inner loop. If there are no swaps, this indicates that all the elements in the array have been sorted.
#
Space ComplexityWe only need some temporary variables to store things like the flag. Hence, space required is in order of O(1)
.