Bubble Sort vs Insertion Sort
Bubble sort is a sorting algorithm that operates by going through the list to be sorted repeatedly while comparing pairs of elements that are adjacent. If a pair of elements is in the wrong order they are swapped to place them in the correct order. This traversal is repeated until no further swaps are required. Insertion sort is also a sorting algorithm, which operates by inserting an element in the input list in to the correct position in a list that is already sorted. This process is applied repeatedly until the list is sorted.
What is Bubble Sort?
Bubble sort is a sorting algorithm that operates by going through the list to be sorted repeatedly while comparing pairs of elements that are adjacent. If a pair of elements is in the wrong order they are swapped to place them in the correct order. This traversal is repeated until no further swaps are required (which means that the list is sorted). Since the smaller elements in the list come to the top as a bubble comes to the surface, it is given the name bubble sort. Bubble sort is a very simple sorting algorithm but it has an average case time complexity of O(n2) when sorting a list with n elements. Due to this, bubble sort is not suitable for sorting lists with a large number of elements. But due its simplicity, bubble sort is taught during introductions to algorithms.
What is Insertion Sort?
Insertion sort is another sorting algorithm, which operates by inserting an element in the input list in to the correct position in a list (that is already sorted). This process is applied repeatedly until the list is sorted. In insertion sort, sorting is carried out in-place. Therefore after the ith iteration of the algorithm, the first i+1 entries in the list will be sorted and the rest of the list will be unsorted. At each iteration, the first element in the unsorted part of the list will be taken and inserted in to the correct place in the sorted section of the list. Insertion sort has an average case time complexity of O(n2). Due to this, insertion sort is also not suitable for sorting large lists.
What is the difference between Bubble Sort and Insertion Sort?
Even though both the bubble sort and insertion sort algorithms have average case time complexities of O(n2), bubble sort is almost all the time outperformed by the insertion sort. This is due to the number of swaps needed by the two algorithms (bubble sorts needs more swaps). But due to the simplicity of bubble sort, its code size is very small. Also there is a variant of insertion sort called the shell sort, which has a time complexity of O(n3/2), which would allow it to be used practically. Furthermore, insertion sort is very efficient for sorting “nearly sorted” lists, when compared with the bubble sort.