edited by
8,636 views
50 votes
50 votes
The minimum number of comparisons required to sort $5$ elements is ______
edited by

3 Answers

Best answer
52 votes
52 votes

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

edited by
2 votes
2 votes

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.

1 votes
1 votes

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

 

1 flag:
✌ Low quality (mayank_1)
Answer:

Related questions

32 votes
32 votes
8 answers
1
Kathleen asked Sep 12, 2014
10,064 views
Consider the following recursive definition of $fib$:fib(n) := if n = 0 then 1 else if n = 1 then 1 else fib(n-1) + fib(n-2)The number of times $fib$ is called (includin...
44 votes
44 votes
2 answers
2
Kathleen asked Sep 12, 2014
13,563 views
The weighted external path length of the binary tree in figure is ______
25 votes
25 votes
5 answers
3
Kathleen asked Sep 12, 2014
8,134 views
Consider the number given by the decimal expression:$$16^3*9 + 16^2*7 + 16*5+3$$The number of $1’s$ in the unsigned binary representation of the number is ______
26 votes
26 votes
5 answers
4
Kathleen asked Sep 12, 2014
6,563 views
Give an optimal algorithm in pseudo-code for sorting a sequence of $n$ numbers which has only $k$ distinct numbers ($k$ is not known a Priori). Give a brief analysis for ...