Insertion Sort vs Selection Sort

In this article, we will discuss insertion sort, Selection sort and the basic differences between these two sorting techniques in detail:

What is Insertion Sort?

Insertion Sort – The insertion sort is one of the simple sorting techniques in which we insert an element of the unsorted array at its correct position in the sorted array.

We can understand the above idea through the given pseudo-code of the Insertion Sort function:

Insertion sort (a[], n)
{
	For j 1 to n-1
	{	
		Key = a[j]
		i = j - 1
		While i > -1 and a[i] > key
		{
			a[i + 1] = a[i]
			i = i – 1
		}
	a[i + 1] = Key
	}
} // Where n is the size of the array

In the above code, we run the for-loop from 1 to n-1 and the while-loop from 0 to j -1, where the value of j depends on the for a loop.

Let us sort an array using the Insertion sort to get the complete idea of it:

Consider an array a[] = {45, 26, 12, 29, 8}. Let us now understand the steps included to sort the given array.

• First Iteration – j = 1, i = 0 to 0, and Key = a[j] = a[1] = 26
  • Here, i > -1 and a[i = 0] = 45 > key = 26. The while-loop condition is satisfied. We execute a[0+1] = a[0] = 45 and i = 0 – 1 = -1. Now the array is like a[] = {45, 45, 12, 29, 8}.
    
  • Now, i = -1, the while loop condition is not satisfied. We execute a[0+1] = 26. The array is like a[] = {26, 45, 12, 29, 8}.

• Second Iteration – j = 2, i = 1 to 0, and key = a[j] = 12
  • i = 1 and a[1] = 45 > key = 12. The while Loop condition is satisfied. We execute a[1+1] = a[1] = 45 and i = 1 – 1 = 0. Now the array is like a[] = {26, 45, 45, 29, 8}.
  • i = 0 and a[0] = 26 > key = 12. The while Loop condition is satisfied. We execute a[0+1] = a[0] = 26 and i = 0 – 1 = -1. Now the array is like a[] = {26, 26, 45, 29, 8}.
  • i = -1. We execute the last statement, a[-1 + 0] = a[0] = key = 12. Now, a[] = {12, 26, 25, 29, 8}.

• Third Iteration – j = 3, i = 2 to 0, and key = a[3] = 29
  • i = 2 and a[2] = 45 > key = 29. The while Loop condition is satisfied. We execute a[2+1] = a[2] = 45 and i = 2 – 1 = 1. Now the array is like a[] = {12, 26, 45, 45, 8}.
  • i = 1 and a[1] = 26 < key = 29. The while loop condition is not satisfied. We execute a[1+1] = key = 29. The array is like a[] = {12, 26, 29, 45, 8}.

• Fourth Iteration – j = 4, i = 3 to 0, and key = a[4] = 8
  • i = 3 and a[3] = 45 > key = 8. The while Loop condition is satisfied. We execute a[3+1] = a[3] = 45 and i = 3 – 1 = 2. Now the array is like a[] = {12, 26, 29, 45, 45}.
  • i = 2 and a[2] = 29 > key = 8. The while Loop condition is satisfied. We execute a[2+1] = a[2] = 29 and i = 2 – 1 = 1. Now the array is like a[] = {12, 26, 29, 29, 45}.
  • i = 1 and a[1] = 26 > key = 8. The while Loop condition is satisfied. We execute a[1+1] = a[1] = 26 and i = 1 – 1 = 0. Now the array is like a[] = {12, 26, 26, 29, 45}.
  • i = 0 and a[0] = 12 > key = 8. The while Loop condition is satisfied. We execute a[0+1] = a[0] = 12 and i = 0 – 1 = -1. Now the array is like a[] = {12, 12, 26, 29, 45}.
  • i = -1. We execute the last statement, a[-1 + 0] = a[0] = key = 8. Now, a[] = {8, 12, 26, 29, 45}.
    
    After complete execution of the Fourth Iteration, we get our sorted array. The above steps are also shown in the figure given below:

What is Selection Sort?

Selection Sort – In this sorting technique, we select the smallest element and replace it with the first element of the unsorted part of the array. The idea is implemented by considering the whole array as two subarrays, one sorted and another unsorted subarray. Initially, the size of the sorted array is taken to zero, and it increases with each iteration and becomes equal to the size of the array after the complete execution.

The size of the unsorted subarray decreases after each iteration and finally becomes zero after complete execution.

The Pseudo-code of the selection sort function is explained below:

Selection Sort (int a[], int n) 
{
    For i = 0 to n - 2 
    {
        Min_index = i; 
        For j = i+1 to n - 1 
        {
            If (a[j] < a[Min_index]) 
                Min_index = j;
        }
        If i != Min_index
       	      swap(a[i], a[Min_index]); 
    }
} // Where Min_index is the index of the minimum element and n is the size of the array.

We can see in the above pseudo-code that the external for loop runs from 0 to n – 2, and the internal for loop runs from i + 1 to n – 1.

Let us sort an array using the selection sort to get a complete overview of this sorting technique:

Consider an unsorted array a[] = {18, 26, 12, 30, 8} of size = 5. The steps included in sorting the given array using selection sort are given below:

• First Iteration – i = 0, j = 0 + 1 to 5 – 1 = 4. Min_index = i = 0.
  • The internal for loop runs and finds the index of the smallest element of the array and updates the value of Min_index. Here, 8 is the smallest element, after execution of the first for loop, Min_index will become equal to 4.
  • Now, we check the if-condition. Here, i = 0 and Min_index = 4, the condition is satisfied. We swap a[i] = 18 with a[min_index] = 8. The smallest element is at its correct position, a[] = {8, 26, 12, 30, 18}

• Second Iteration – i = 1, j = 2 to 4, Min_index = 1
  • The smallest element in the unsorted subarray is 12 at index = 2. After complete execution of the internal for-loop, Min_index will become equal to 2.
  • We check the if-condition. Here, i = 1 and min_index = 2. The if-conditioned is satisfied. We swap a[i] = 26 and a[Min_index] = 12. The second smallest value reaches to its correct position in the sorted array, a[] = {8, 12, 26, 30, 18}.

• Third Iteration – i = 2, j = 3 to 4, Min_index = 2
  • The smallest value in the unsorted subarray is 28, which is at index = 4. After executing the internal for-loop, the Min_index will become equal to 4.
  • We check the if-condition. Here, i = 2 and min_index = 4. The if-conditioned is satisfied. We swap a[i] = 26 and a[Min_index] = 18. The third smallest value reaches to its correct position in the sorted array, a[] = {8, 12, 18, 30, 26}.

• Fourth Iteration – i = 3, j = 4 to 4, Min_index = 3
  • The smallest value in the unsorted subarray is 26 at index = 4. After executing the internal for-loop. The Min_index will become equal to 4.
  • We check the if-condition. Here, i = 3 and min_index = 4. The if-conditioned is satisfied. We swap a[i] = 30 and a[Min_index] = 26. The fourth smallest value reaches to its correct position and also the largest element reaches to its correct position in the sorted array, a[] = {8, 12, 18, 30, 26}.

After complete execution of the program, we get the sorted array as an output.

Difference between Insertion Sort and Selection Sort

The main differences between insertion sort and selection sort are listed below in the table:

	Insertion Sort	Selection Sort
Idea / Approach	The idea behind this sorting algorithm is that it inserts the first element of the unsorted subarray in the sorted subarray at its correct position.	The idea behind this sorting algorithm is that it selects the minimum element from the unsorted array and replaces it with its first element.
Time Complexities	When we pass a sorted array to the insertion sort function, its time complexity becomes O(n). Its average and worst time complexities are O(n^2).	The best, average and worst-case time complexities are O(n^2). It runs n^2 times for all cases.
Space complexity	In the worst case, its space complexity is T(n) = O(1) as it does not require extra space to sort an array.	In the worst case, its space complexity is also T(n) = O(1).
Efficiency	Insertion sort is more efficient than Selection Sort.	Less efficient than Insertion Sort.
Stability	It is a stable sorting algorithm as the order of equal elements remains preserved.	It is an unstable sorting algorithm as the order of equal elements remains unpreserved.
Speed	Faster than the selection sort.	Slower than the insertion sort.
Method	It follows the incremental approach.	It follows the selection approach.