4 votes 4 votes We need to sort 7 numbers each of 4 digits. What is the number of comparisons in worst case . Options are as follows: 1) 40 2) 38 3) 47 4) 280 DS sorting + – Nisha kumari asked Jun 4, 2017 Nisha kumari 1.2k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Devshree Dubey commented Jun 4, 2017 reply Follow Share It should depend on the sorting algo used. Isn't it??Any mention of the algorithm that is used?? 1 votes 1 votes Arnab Bhadra commented Jun 20, 2017 reply Follow Share Which algorithm do you want to use? And in the question statement , there are 7 number and 4 digit that implies radix sort is preferable. Radix sort is not a Comparison based sort. If we apply radix sort, no of Comparisons is zero. 0 votes 0 votes Arjun commented Jun 20, 2017 reply Follow Share Leave the digits - then answer will be ? 1 votes 1 votes just_bhavana commented Jun 20, 2017 reply Follow Share nlogn as it is the tightest upper bound as well as lower bound on number of comparisons in comparison based sorting. For n = 7, it is $\approx$ 20 0 votes 0 votes junaid ahmad commented Jun 20, 2017 reply Follow Share I am getting 28 using insertion sort as no of comparison n(n+1)/2 and n=7. 1 votes 1 votes Arnab Bhadra commented Jun 20, 2017 reply Follow Share No of Comparison in insertion sort n*(n-1)/2 1 votes 1 votes Arnab Bhadra commented Jun 20, 2017 reply Follow Share As per my knowledge is concerned, nlogn is not tightest upper bound of no of comparisons. 0 votes 0 votes just_bhavana commented Jun 20, 2017 reply Follow Share Reference https://en.wikipedia.org/wiki/Comparison_sort#Lower_bound_for_the_average_number_of_comparisons 0 votes 0 votes Arnab Bhadra commented Jun 20, 2017 i edited by Arnab Bhadra Jun 20, 2017 reply Follow Share Lower bound of no of comparison of a comparison based sorting is Ω(nlogn). This means minimum nlogn comparisons is required to sort. It is not upper bound. 0 votes 0 votes theanindya commented Jul 28, 2017 reply Follow Share can you please expain how no of comparison in insertion sort is n(n-1)/2?? As no of comparison and no of movements are n in insertion sort asii know.i may be wrong! 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes In Worst case, total no of comparison in bubble sort , Insertion sort is n*(n-1)/2 where n = no of elements. so here n=7. No of Comparison = 7*6/2 = 21 Link : https://www.cise.ufl.edu/~sahni/cop3530/slides/lec026.pdf Arnab Bhadra answered Jun 20, 2017 Arnab Bhadra comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes https://stackoverflow.com/questions/11752564/how-many-comparisons-are-needed-in-worst-case-if-we-have-to-sort-7-numbers-each Mohitkumaraiactr answered Jun 30, 2017 Mohitkumaraiactr comment Share Follow See all 0 reply Please log in or register to add a comment.