Minimum number of comparisons required to sort 5 elements is

Question

The minimum number of comparisons required to sort 5 elements is -

• A. 4
• B. 5
• C. 6
• D. 7

Comments

If we apply tournament method to sort 5 elements then,

1.5n-1.5

1.5(5) - 1.5 = 6

Is this approach correct ?

Answer 1

Can be done using insertion sort. Insertion sort takes n²/4 comparisons in average case so answert would be 7 but since here we are not given average/worst case, so go with Counting sort.

Answer 2

By using merge sort, the minimum no of comparison is equal to ceiling logn!.

Here n=5. So minimum number of comparison =7

Answer 3

log( n!) for n elements.so log 120 upper seal is 7

 

Answer 4

There are 5 elements. 

You need to ask yourself the possible combinations of these 5 elements. 

eg. Let's say there are just 2 elements(3,4) then what are the possible arrangements 

• 3, 4
• 4, 3

One of them is sorted say (3, 4)

Similarly for 5 elements (1,2,3,4,5) is the sorted arrangement but what are the other possible such patterns

few of them are 

• 2,3,4,5,1
• 1,2,4,5,3
• 4,1,3,2,5
• 5,4,3,1,2

1st number, 2nd number, 3rd number, 4th number, 5th number

for 1st number I can pick any of the 5 numbers from 1,2,3,4,5 -> picked 5 (1,2,3,4) left

for 2nd number I can pick any of the 4 numbers remaining from 1,2,3,4 -> picked 2 , (1,3,4) left

for 3rd number I can pick any of the 3 numbers remaining from 1,3,4 -> picked 4 , (1,3) left

for 4th number I can pick any of the 2 numbers remaining from 1,3 -> picked 1 , (3) left

for 5th number I can only pick 3

Turns out there are 5! such arrangements that is 120

let's say the arrangement

• 1,2,4,3,5 is represented as 1 in binary
• 1,2,3,5,4 is represented as 10 in binary 
• 1,3,2,5,4 is represented as 11 in binary
• 1,4,5,3,2 is represented as 100 in binary
• .
• .
• .
• 1,2,3,4,5 is represented as 1111000 in binary

so we would need 7 binary bits to represent all the patterns and one of them is our desired sorted arrangement.

If there is a checker who verifies our given output with the binary representation then she would have to check 7 bits. 

if there is no checker then we can output the given number as it is and we can argue that our output is correct since no one is going to check. 

 

//now how would you make sure to output the correct answer every time. 

You can act as a checker and with every bit you check you are eliminating half of the possible arrangements (2^7/2) after you check 7 bits you would left with just 1 arrangement and that is your answer. 

 

That's how you get log(120)