Difference Among Bubble Sort, Selection Sort, and Insertion Sort

Before starting with the difference among their types, you need to know what sorting is and why it is required. Sorting is the process of arranging items according to particular criteria. It arranges the items in sequence. It helps in grouping and categorizing items with identical properties. We often use the sort option while searching anything on a website or applications for sequencing it based on their price, warranty, newer first, etc which helps us to choose our desired product easily. Technically, Sorting is an algorithm used in computer languages to rearrange elements in a list or array. Bubble sort, Selection sort, and Insertion sort are three basic types of sorting algorithms that differ in their mechanism and time and space complexities.

Difference Among Bubble Sort, Selection Sort, and Insertion Sort

What is the difference between Bubble sort, Selection sort, and Insertion sort?

In Bubble sort, adjacent elements of an unsorted list or array are compared and swapped if the condition is true .Whereas, in Selection sort, the smallest element of the list is selected through traversal of the loop, and then it is swapped against the largest element and in Insertion sort, the array is divided into 2 parts of which one is sorted part and other is an unsorted part, one by element from unsorted part is taken and placed in sorted part in its rightful sorting position.     

Bubble sort is the least efficient than the other two when a large set of input is given. It has the best case time complexity of O(n), for optimized sort. Selection sort has improved efficiency than bubble sort and is also faster. It has a time complexity of O(n2) for the best case. Insertion sort has the best case complexity of O(n) and it does not need to get into the inner loop if the array is already sorted.

Bubble Sort

As discussed before, bubble sort is an algorithm that considers two adjacent elements in an array and swaps them if the sequence is incorrect. As the largest element when sorting in ascending order after each pass is directed to the last position, it is called bubble sort. It is not suitable for large input data because of its high average and worst-case complexity.

Working:Example Array = [9, 3, 2, 6, 5]First pass  [9, 3, 2, 6, 5]  🡪  [3, 9, 2, 6, 5]   {As 9>3} [3, 9, 2, 6, 5]  🡪 [3, 2, 9, 6, 5]    {As 9>2} [3, 2, 9, 6, 5]🡪 [3, 2, 6, 9, 5]    {As 9>6} [3, 2, 6, 9, 5] 🡪 [3, 2, 6, 5, 9]   {As 9>5}{9(greatest element) is inserted to its correct position of sorting in first pass.} Second pass [3, 2, 6, 5, 9] 🡪 [2, 3, 6, 5, 9]   {As 3>2} [2, 3, 6, 5, 9] 🡪 [2, 3, 6, 5, 9] [2, 3, 6, 5, 9] 🡪 [2, 3, 5, 6, 9]   {As 6>5}Third pass [2, 3, 5, 6, 9] is a sorted array now. The algorithm needs the whole pass without any pass to know it is completed. Therefore thirds pass will go without any swapping but there will be a comparison among two adjacent pairs.

Selection Sort

The selection sort algorithm finds the minimum element of the array and starts putting it at the beginning repeatedly. It has to maintain two sub-arrays, one is sorted and the other is unsorted. In each pass of the algorithm, one element from the unsorted array is taken and is positioned at its correct position in the sorted array.

Working:Taking the same example arrayArray = [9, 3, 2, 6, 5]First Pass (minimum = 2) [9, 3, 2, 6, 5] 🡪 [2, 3, 9, 6, 5]   {9 is replaced by 2}Second pass (minimum = 3) [2, 3, 9, 6, 5] 🡪 [2, 3, 9, 6, 5]   {3 is already in correct position}Third Pass (minimum = 5) [2, 3, 9, 6, 5] 🡪 [2, 3, 5, 6, 9]   {9 is replaced by 5}Forth pass (minimum = 6) [2, 3, 5, 6, 9] 🡪 [2, 3, 5, 6, 9]   {6 is already in correct position}Fifth Pass (minimum = 9) As the last minimum and largest value of the array is automatically positioned at the last index, the array is sorted now. [2, 3, 5, 6, 9]

Insertion Sort

It is a simple algorithm that virtually divides the algorithm into the sorted and the unsorted part. It is then followed by picking values from the unsorted part and putting them in the sorted part at their correct position. It is efficient for small input data. It is best in the average case where data is partially sorted.   

Working:

Array = [9, 3, 2, 6, 5]

First pass

[9, 3, 2, 6, 5] 🡪 [3, 9, 2, 6, 5] 

For now, 3 is the sorted part of the array.

Second pass

[3, 9, 2, 6, 5] 🡪 [3, 2, 9, 6, 5]

After swapping, 3 and 2 are not sorted, thus swap again.

[3, 2, 9, 6, 5] 🡪 [2, 3, 9, 6, 5]

Third pass

[2, 3, 9, 6, 5] 🡪 [2, 3, 6, 9, 5]

Forth pass

[2, 3, 6, 9, 5] 🡪 [2, 3, 6, 5, 9]

After swapping, 6 and 5 are not sorted, thus swap again.

[2, 3, 6, 5, 9] 🡪 [2, 3, 5, 6, 9]

Hence [2, 3, 5, 6, 9] is a sorted array.

Conclusion

Sorting AlgorithmTime complexitySpace complexity
Best caseAverage caseWorst caseWorst case
Insertion sortO(n)O(n2)O(n2)O(1)
Selection sortO(n2)O(n2)O(n2)O(1)
Bubble sortO(n)O(n2)O(n2)O(1)

Therefore, Bubble sort, insertion sort or, selection sort is used for sorting purposes based on their relevance according to their time and space complexities. 

FAQs
  1. Which of the following is a non-stable sorting technique among these three?

Answer: Selection sort

  1. What is the number of passes required to sort an array of n elements by Insertion sort?

Answer: n-1 number of passes are required for sorting an array of n elements by insertion sort.

  1. What is the total number of comparisons in bubble sort?

Answer:  n(n-1)/2

  1. What is the best case in bubble sort?

Answer: The best case of bubble sort is when the array seems to be sorted already.

  1. Which is better insertion sort or selection sort?

Answer: Insertion sort is more efficient if the array is already sorted or close to sorted.

  Selection sort is preferred if writing to memory is more expensive than reading.

  1. Where is bubble sort used?

Answer: It is used for educational purposes for understanding the foundation of sorting.

  1. What is the complexity of bubble sort?

Answer: The bubble sort algorithm has a worst-case time complexity of O(n2).

  1. Which is the better selection sort or the bubble sort?

Answer: Selection sort is better as it performs faster and more efficiently.

Difference Among Bubble Sort, Selection Sort, and Insertion Sort

Leave a Reply

Your email address will not be published. Required fields are marked *

Scroll to top