5,005 views
The minimum number of comparisons required to sort $5$ elements is ______

edited by

Some Important points from wiki -->

https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

• If the algorithm always completes after at most f(n) steps, it cannot distinguish more than 2f(n) cases because the keys are distinct and each comparison has only two possible outcomes.
• Determining the exact number of comparisons needed to sort a given number of entries is a computationally hard problem even for small n, and no simple formula for the solution is known.

Important point, they may ask in GATE in future.

@smsubham, I did not understand it :(.. What if it is n=12 elements. logn! is much greater than merge sort i.e, nlogn..
O(log(n!)) == O(log(n^n)) == O(nlogn) , for very large values of n.  @pranavsettaluri9

### Subscribe to GO Classes for GATE CSE 2022

The answer is $7.$

Minimum number of comparisons $= \lceil \log(n!) \rceil = \lceil \log(5!) \rceil = \lceil \log(120) \rceil = 7.$

Reference: http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

See the above link. The technique is given by Knuth :)
But of array is sorted and i use insertion sort it will take 4 comparisions?
Yes if we use insertion sort on already sorted array of n it takes n-1 comparisons.
Yes.
even bubble sort on already sorted array will give 4 comparisons right ?
@Arjun sir, here we are answering for the worst case, right? Otherwise, if array is sorted and I use insertion sort it will take 4 comparisions, right?
I am also getting 4 as answer as minimum comparison is being asked.
Didn't understand from the links given in the answer.

Can someone plz explain in simple terms?
Not clear about the given answer. I think it should be 4.
I didn't got the explanation can someone help?
I think, lower bound is asked, it will be log(n!) only.

lower order is generally given for a problem not for an algorithm.

Lower bound of a problem means best algo that can solve the problem(in every case).
The question asks for the minimum number of comparisons required to sort any input of size 5, not just the sorted input of size 5. Hence 4 would not be the correct answer.
@minipanda link is not working
why people said like sorted array then insertion sorting would take o(n) comparisons it doesn't mentioned in question they talked general case that provide us  min number of comparisons that's it...

This is one of the simple ways. Do not go with any specific algorithm as none conditions are specified, i.e. the least comparisons or max. comparisons etc.

There are 5 elements to be compared, then 5! ways are possible in which the elements could be present in the input. This equals 120 ways.

Now, for comparison we require exactly 2 elements at a time. Therefore, in 2**x ways we can compare the elements present in any 120 ways possible.

Therefore,  2**x == 120 ==> x=7.

Therefore, comparisons are enough.

I do not understand the calculation pls help me .
“In 2**x ways we can compare the elements present in any 120 ways possible.”

can you explain this part?

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).

cant it be 4. if we apply insertion sort to almost sorted array. like 2,1,3,4,5 and we apply insertion sort.

.

as they havent mentioned abt any sorting procedure of arrangement of element.
Yes, in this case it's 4 :O
I need to relook now.
as they havenot mentioned any criteria so i am confused :/
Give me some time and I'll look into it
I think question could have been described more.

If the array is already sorted then O(1) time and only 4 comparisons are needed.

Not to be ambiguous , i am taking both the extreme cases :

my confusion :
Sorted :
n-1 comparison
Reverse sorted :
n(n-1)/2 comparison.

( considering only inplace algo)

where this log(n!) coming from?

edited by
For those who are confused that why not the result is coming through insertion,heap or merge sort.

It is a special case where all the above algorithm will not give correct result.For this question you have to make a specific Algorithm.

And if you are confuse  how log n!  it is then you have to read the whole research paper for that.If you want to learn about that open the link provided by Arjun suresh sir.