19 votes 19 votes The minimum number of comparisons required to sort 5 elements is - 4 5 6 7 Algorithms algorithms sorting + – piyushkr asked Dec 30, 2015 • retagged Jun 17, 2022 by makhdoom ghaya piyushkr 43.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply syncronizing commented Sep 13, 2018 reply Follow Share If we apply tournament method to sort 5 elements then, 1.5n-1.5 1.5(5) - 1.5 = 6 Is this approach correct ? 0 votes 0 votes Please log in or register to add a comment.
Best answer 25 votes 25 votes Minimum number of comparisons = ⌈ log (n!)⌉ = ⌈log(5!)⌉ =⌈log(120)⌉ = 7Ref:http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list Ashish Gupta answered Dec 30, 2015 • selected Dec 30, 2015 by Arjun Ashish Gupta comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Shatadru RC commented Oct 7, 2017 reply Follow Share Ans is 4 when u take base 10 0 votes 0 votes Bad_Doctor commented Nov 2, 2017 reply Follow Share 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 ) . 3 votes 3 votes dd commented Dec 29, 2017 reply Follow Share https://gateoverflow.in/95725/algorithm-minimum-comparison-sorting#a95826 2 votes 2 votes Please log in or register to add a comment.
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 s_raj answered Jun 16, 2017 s_raj comment Share Follow See all 0 reply Please log in or register to add a comment.
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] Yugul Pandey answered Feb 24, 2020 Yugul Pandey comment Share Follow See all 2 Comments See all 2 2 Comments reply Mohitac commented Mar 30, 2020 reply Follow Share 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. 0 votes 0 votes blitu12345 commented Aug 2, 2020 reply Follow Share No its wrong. For min number we will look at the worst case. 2 votes 2 votes Please log in or register to add a comment.
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 rish1602 answered Jul 10, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.