Sorting Algorithm: Bubble Sort
Bubble Sort, is one of the most basic sorting algorithm. It works by swapping elements until they are in right order. Here are the steps the algorithm would follow.
The Steps:
- Compare first and second element.
- Swap the lesser of the two closer to the start of the list, while the other to the left.
- Compare the next two (2nd and 3rd) elements, and swap if necessary.
- Repeat until no more swaps are needed.
Example:
Suppose we have a list l1 = [1,4,5,3]
- Compare elements 1 and 4. Since the greater of the two is to the right (closer to the end) no swap is needed.
- Compare elements 4 and 5. Again the larger of the two elements is closer to the end so no swap is needed.
- Compare elements 5 and 3, now the lesser of the two elements gets swapped to the left.
- After first pass (iteration/repetition) our list becomes: [1,4,3,5].
Note: After first pass the greatest element is at the end of the list, so essentially we are reverse ordering the list.
5. Compare 1 and 4, no swap needed.
6. Compare 4 and 3, swap needed, the lesser of the two goes to the left.
7. compare 4 and 5, no swap needed.
8. End of second pass [1,3,4,5]
There we go, we have our sorted list. Here is the python implementation of Bubble Sort.
We first start a for loop to go repeat the process n times, since we have n elements. Inside the first for loop, we have another for loop, which is not repeated n times but rather, n-i-1 times. Which means, we only need to check for n-i-1 elements each time. This saves us time, for example at the end of first pass the largest number ends up at the end of the list anyways, so we avoid checking it. Then at the end of second pass the last two elements are at the right place and so on. Inside the for loop we do a simple mechanism of swapping by comparing elements.
Time Complexity: Let us say the list is in reverse order, in that case: in the first pass, the algorithm would do n-1 comparisons. At the end of the second pass it would do n-2 comparisons. and so on. So the total number of comparisons would be:
n-1 + n-2 + n-3 + n-4+……+1
This is a series with sum = n(n-1)/2 which results in a time complexity of O(N²).
Hence the time complexity of bubble sort is O(N²).
Space Complexity: Space complexity for bubble sort is O(1), since there is no storage of numbers and just swapping based on comparisons.
What do these complexities mean?
A time complexity of O(N²) means with input the number of steps increase quadratically.
For 10 steps, there might be 100 comparisons.
For 20 Steps, there might be 400 comparisons.
While a space complexity of O(1), refers to constant space complexity, since we are not really using any copy or duplicates.
