The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
1.8k views
The minimum number of comparisons required to sort $5$ elements is ____
asked in Algorithms by Veteran (59.8k points)
edited by | 1.8k views
+2

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.

2 Answers

+28 votes
Best answer

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

answered by Boss (34.1k points)
edited by
0
See the above link. The technique is given by Knuth :)
+6
But of array is sorted and i use insertion sort it will take 4 comparisions?
0
Yes if we use insertion sort on already sorted array of n it takes n-1 comparisons.
0
Yes.
+1
even bubble sort on already sorted array will give 4 comparisons right ?
0
@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?
0
I am also getting 4 as answer as minimum comparison is being asked.
0
Didn't understand from the links given in the answer.

Can someone plz explain in simple terms?
0
Not clear about the given answer. I think it should be 4.
0
I didn't got the explanation can someone help?
+1
0
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).
0
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.
+1 vote

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

 

answered by Boss (23k points)
0
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.
0
Yes, in this case it's 4 :O
I need to relook now.
0
as they havenot mentioned any criteria so i am confused :/
0
Give me some time and I'll look into it
0
I think question could have been described more.

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

@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?

0
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.
Answer:

Related questions

+2 votes
1 answer
7
asked Sep 11, 2014 in Non GATE by Kathleen Veteran (59.8k points) | 445 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,003 questions
51,321 answers
177,481 comments
66,665 users