It is asked minimum number of comparisons to sort 5 elements
Insertion sort performs the minimum number of comparisons to sort 5 elements
Assuming my array is almost sorted (but not completely sorted)
A[0] |
A[1] |
A[2] |
A[3] |
A[4] |
2 |
3 |
4 |
5 |
1 |
Now my insertion sort runs from 1 to 4 indices of the array as elements A[0..j-1] are assumed to be sorted and at the start of the algorithm, j=1 so A[0,,,0] contains only one element, so it is sorted.
Now I compare 3 with 2 and check if 3 is less? (No)--1 Comparison
Array A[0,1] sorted.
Now again A[2] compared with A[1].3<4. No Swap required. 1 Comparison.
Similarly one comparison for A[3].
Now When I need to put A[4] into the correct place, How many comparisons do I need to make before 1 is placed in correct position?
1 Comparison with 5 and 1 swap so now array becomes
A[0] |
A[1] |
A[2] |
A[3] |
A[4] |
2 |
3 |
4 |
1 |
5 |
Now again 1 comparison among A[2] and A[3] and they are swapped(1 Swap).
A[0] |
A[1] |
A[2] |
A[3] |
A[4] |
2 |
3 |
1 |
4 |
5 |
And so sort array 2 more comparisons and 2 more swaps and array finally is
A[0] |
A[1] |
A[2] |
A[3] |
A[4] |
1 |
2 |
3 |
4 |
5 |
So, total comparisons=7, total swaps=4.
So, minimum comparisons to sort the array is 7 assuming the array is almost sorted but not completely sorted.
So I think question asks this only, assuming array to be not completely sorted, but almost sorted(means some elements are in correct order).
Answer-7