Bubble Sort vs Selection 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. Selection sort is also a sorting algorithm, which starts by finding the minimum element in the list and swapping it with the first element. This process is repeated for the remainder of the list by placing swapped elements in order.
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 Selection Sort?
Selection sort is also another sorting algorithm that starts by finding the minimum element in the list and swapping it with the first element. Then the minimum element is found from the remainder of the list (from the second element until the last element in the list) and swapped with the second element. This process is repeated for the remainder of the list by placing swapped elements in order. So in selection sort, at any step of the algorithm, the list is divided in to two parts where one part contains sorted elements and the other part contains unsorted elements. As the algorithm proceeds, the sorted list grows from left to right. Selection sort also has an average case time complexity of O(n2). Therefore it is also not suitable for sorting large lists.
What is the difference between Bubble Sort and Selection Sort?
Even though both the bubble sort and selection sort algorithms have average case time complexities of O(n2), bubble sort is almost all time outperformed by the selection 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. Stability is another difference in these two algorithms. A stable sorting algorithm, is a sorting algorithm that retains order of records if the list contains elements with an equal value. In that sense, selection sort is not a stable algorithm whereas bubble sort is a stable algorithm.