retagged by
43,407 views
19 votes
19 votes

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

  1. 4
  2. 5
  3. 6
  4. 7
retagged by

8 Answers

Best answer
25 votes
25 votes

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

selected by
3 votes
3 votes

minimum number of comparison is= log(n!)

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

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

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

1 votes
1 votes
Answer Should Be 4.

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

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

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

Related questions

2 votes
2 votes
1 answer
1
yes asked Oct 6, 2015
1,331 views
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)
0 votes
0 votes
2 answers
2
dhruba asked Jun 5, 2023
1,093 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
0 votes
0 votes
1 answer
3
Siddhi Viradiya asked Apr 3, 2016
1,791 views
i cannot understand the following explanation..how solution is (3/2)n-2???If n is a power of 2, then we can write T(n) as:T(n) = 2T(n/2) + 2After solving above recursion,...
1 votes
1 votes
1 answer
4
iarnav asked May 4, 2019
834 views
I’ve seen this wikipedia article – https://en.wikipedia.org/wiki/Comparison_sortAlso see this link – https://gateoverflow.in/32948/minimum-number-of-comparisonshttp...