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

Minimum number of comparisons = ⌈ log (n!)⌉ = ⌈log(5!)⌉ =⌈log(120)⌉ = 7

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

Comments

Ans is 4 when u take base 10

---

That is Sterling's approximation. 

This is actual conversion:

log 2 ⁡ ( n ! ) = n log 2 ⁡ n − ( log 2 ⁡ e ) n + O ( log ⁡ n ) = Ω ( n log 2 ⁡ n ) .

---

https://gateoverflow.in/95725/algorithm-minimum-comparison-sorting#a95826

Answer 2

minimum number of comparison is= log(n!)

so, ceil(log(n!))= ceil(log(nⁿ) 

=>ceil(log(nⁿ))= ceil(nlog(n))

=>ceil(5log(5))= 4 which is option a

Answer 3

Answer Should Be 4.

this is a best case(Sorted Array) of insertion sort.

Comparisons =n-1.[Best Case of Insertion Sort]

Comments

Minimum number of cases are possible in the best case and that will be when it is already sorted and we are using insertion sort. This will take n-1 comparisons. If you find my understanding incorrect then please reply.

---

No its wrong. For min number we will look at the worst case.

Answer 4

consider a discrete variate x which implies the number of elements in the array. Now either the elements can either be sorted or unsorted, hence probablity is ½

x=     1     2      3       4        5

p=    ½    ½     ½      ½        ½  

hence expected mean or expected number of comparisons=   1(1/2) +2(1/2)  + 3(1/2)   + 4(1/2) + 4(1/2)     = 7(approx)

Thus around 7 comparisons required