Concept:
Insertion sort:
Insertion sort is a basic sorting algorithm that operates in the same manner that you arrange cards in your hands. The array is divided into two halves, one sorted and one not. Values from the unsorted section are selected and placed in the sorted section at the appropriate location.
The given array is,
Input: 20, 16, 12, 8, 4, 1
Output:1, 4, 8, 12, 16, 20
Pass 1:
Consider the key is 16 and move the elements of array index 1 to 0
swaps are required because 20 is greater than 16.
Swap the elements 20 and 16
16, 20, 12, 8, 4, 1
No swaps are required because till array 1 index is sorted in order.
16, 20, 12, 8, 4, 1
Total swaps are = 1
Pass 2:
Consider the key is 12 and move the elements of array index 2 to 0
swaps are required because 20 is greater than 12.
Swap the elements 20 and 12
16, 12, 20, 8, 4, 1
swaps are required because 16 is greater than 12.
Swap the elements 16 and 12
12, 16, 20, 8, 4, 1
No swaps are required because till the array 2 index is sorted in order.
12, 16, 20, 8, 4, 1
Total swaps are=3
Pass 3:
Consider the key is 8 and move the elements of array index 3 to 0
swaps are required because 20 is greater than 8.
Swap the elements 20 and 8
12, 16, 8, 20, 4, 1
swaps are required because 16 is greater than 8.
Swap the elements 16 and 8
12, 8, 16, 20, 4, 1
swaps are required because 12 is greater than 8.
Swap the elements 12 and 8
8, 12, 16, 20, 4, 1
No swaps are required because till array 3 index is sorted in order.
8, 12, 16, 20, 4, 1
Total swaps are=6
Pass 4:
Consider the key is 4 and move the elements of array index 4 to 0
swaps are required because 20 is greater than 4.
Swap the elements 20 and 4
8, 12, 16, 4, 20, 1
swaps are required because 16 is greater than 4.
Swap the elements 16 and 4
8, 12, 4, 16, 20, 1
swaps are required because 12 is greater than 4.
Swap the elements 12 and 4
8, 4, 12, 16, 20, 1
swaps are required because 8 is greater than 4.
Swap the elements 8 and 4
4, 8, 12, 16, 20, 1
No swaps are required because till array 4 index is sorted in order.
4, 8, 12, 16, 20, 1
Total swaps are=10
Pass 5:
Consider the key is 1 and move the elements of array index 5 to 0
swaps are required because 20 is greater than 1.
Swap the elements 20 and 1
4, 8, 12, 16, 1, 20
swaps are required because 16 is greater than 1.
Swap the elements 16 and 1
4, 8, 12, 1, 16, 20
swaps are required because 12 is greater than 1.
Swap the elements 12 and 1
4, 8, 1, 12, 16, 20
swaps are required because 8 is greater than 1.
Swap the elements 8 and 1
4, 1, 8, 12, 16, 20
swaps are required because 4 is greater than 1.
Swap the elements 4 and 1
1, 4, 8, 12, 16, 20
No swaps are required because till array 5 index is sorted in order.
1, 4, 8, 12, 16, 20
Total swaps are=15
The sorted array is
1, 4, 8, 12, 16, 20
Hence the correct answer is 4, 8, 12, 16, 20, 1.