Sorting techniques in Golang with testing! Part-1 [Bubble Sort]
Bubble Sort
Bubble sort is the most commonly known sorting technique. In each iteration, it compares the adjacent element and swaps them if they are in wrong order.
Implementation of Bubble Sort to sort the elements in ascending order is shown in the below code along with table driven test.
Here I have used table driven test. Table driven tests are useful when you want to build a test cases that can be tested in the same manner. The only difference between normal test and table driven test is that we create a anonymous []struct with fields input and expected(as shown in line 9). Then we fill the test cases and iterate over them. If you wanna know why table driven test and why most of the Golang specs are written in table driven style here is a blog which is beautifully explained by Dave Cheney.
Why the variable swapped is used?
In order to check if the input list is sorted, variable swapped is used. Well, the algorithm still works without swapped variable. But the only reason is the algorithm will stop if it didn’t even swap one element also meaning the list has reached into ordered elements. The best case would be O(n) if it stops first or it increases gradually.
Time complexity of Bubble Sort
Time complexity refers to the amount of time taken by an algorithm or a piece of code to process the given input.
Best case scenario: If the given input is already in sorted form then the time complexity of bubble sort will be O(n) where n is number of elements in the input.
Why O(n)? Because it makes n comparisons.
worst case scenario: If the algorithm is designed to sort in either ascending/descending order and the given input is in reverse order then the time complexity will be O(n²).
How O(n²)? Well, in Bubble Sort (n -1) comparisons is done in 1st pass, (n-2) comparisons in 2nd pass and so on. So,
T(n) = (n-1) + (n-2) + (n-3) +.....+ 3 + 2 + 1T(n) = n (n-1)/2T(n) = n² - n (ignore 1/2 because it’s a constant)i.e O(n²) (because n² is larger than n)
For example if input list = (1, 2, 3, 4), it requires no swapping of adjacent elements i. e swapped will remain false. Hence the time complexity is O(i=1 * j=n) =>O(1n) which is the best case. Say if the input list = (1, 2, 4, 3), it requires one swapping (i. e swapping of 3 and 4). Hence time complexity will be O(i=2 * j=n)=>O(2n). Similarly if input list = (4, 3, 2, 1) then all the elements must be swapped to get order list and time complexity will be O(i=n*j=n) => O(n²) where n is the number of elements in the list.
Pros
- Bubble sort is easy to understand.
- O(n) time complexity in best case.
Cons
- Bubble sort is slow and not suitable if the input is really large.
- It’s time complexity is O(n²) in worst case which is not efficient when compared to other sorting techniques.
Conclusion
In this article we have learnt the implementation of bubble sort along with table driven test, it’s time complexity and pros and cons of Bubble Sort. Please feel free to check the code here and suggest changes by adding comment.
We will see in coming up posts how every standard algorithm is implemented along with their time complexity.
If you liked this article and if it helped you, do give some claps!👏
