GATE CSE 1991 | Question: 01,vii

Question

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

Comments

@Pranavpurkar As, $2^k$ array can be broken down in parts of $2$, at merged at last. This is the procedure they followed in the above link.

---

@Abhrajyoti00 Is the above formula which you mentioned for minimum and maximum number of comparisons is always fixed irrespective of which sorting algorithm is used?

---

@Nandhakumar yes this is true for all comparison based sorting algo.

Answer 1

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

Comments

http://stackoverflow.com/questions/1935194/sorting-an-array-with-minimal-number-of-comparisons

---

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?

---

Best explanation that I found http://ace.cs.ohiou.edu/~razvan/courses/cs4040/lecture09.pdf

 

---

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

Answer 2

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, 7 comparisons are enough.

Comments

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?

Answer 3

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

 

Comments

I think question could have been described more.

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

---

@Ayush Upadhyaya 

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?

---

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.