Bubble Sort vs Insertion Sort: An Average Programmers Dilemma
From the dawn of programming, data has always been a key component to develop anything software-based. From building applications to algorithms and scripts all require data so that they can be tested and debugged. However, an issue arises when data is to be managed and used efficiently. This is where Sorting comes into place. Sorting Algorithms are the most widely used concept in today’s world, they can be used to shape data as per your own needs.
For some of the most average programmers, there is always a dilemma of whether one should use bubble sort or insertion sort. Since not everyone can be a genius programmer, mediocrity always criples in. However, it should be the task of an intelligent project lead to get the best out of the most average programmers. Hence, this article can be treated as a guide for average programmers.
Bubble Sort
Bubble sort is the most basic and easy to implement sorting algorithm. It has a simple working: Given an array of data, we traverse throughout the array one by one comparing the current element to its adjacent one and swapping them when needed. Let’s say we have an element x and its adjacent element in the array is y. If x is greater than y (x>y) then we swap the position of the two elements in the array. Below is an example for the application of bubble sort:
As you can see above, we have an array of 4 elements in no particular order. However, we are asked to sort them in ascending order. So we begin with the first element which is 4 and compare it with its adjacent element which is 3. Since 4 is larger than 3 we need to swap these elements.
Hence, after the swap the array should look like this:
As we can see in the final array there is no need to make any other swaps since the array is already in ascending order.
Time Complexity: Since we always consider worst-case scenarios while calculating time complexity. Here it may be possible that we may have to traverse throughout the entire array for it to be sorted hence the complexity becomes O(n²).
Insertion Sort
Insertion sort is similar to bubble sort where we have a given array and we iterate throughout the array and compare the current element to the ones preceding it. If the current element is smaller than the preceding elements then we swap. For instance, if we’ve elements a, b and c. Assuming that c is smaller than both a and b we first swap it with b and then with a. Below is an example of insertion sort:
Now in the second iteration, we can see that 3 is smaller than the preceding 4 hence we swap them, and after that, in the third iteration, we see that 2 is smaller than the preceding 3 and 4 and hence we make 2 swaps.
After these swaps the finally array starts to look like:
For insertion sort, the worst case arises when the array is sorted in reverse order. If this is the case then we have to traverse through the entire array and sort each element one by one. This creates a time complexity of O(n²).
What to use when
After reading the working of the above 2 sorting algorithms, it may have become difficult for you to determine which one is to be used when and which one gives better performance. Bubble sort is the easiest algorithm to implement and hence is used in cases where the given data is very small and time doesn’t matter. However, in cases where the array size is a bit larger and we need better performance, we can use insertion sort.