in Graph Theory
235 views
0 votes
0 votes
Find the least number of comparisons needed to sort five element.

 

I AM GETTING 7 AS (LOG 5!) =7........
in Graph Theory
by
235 views

1 Answer

0 votes
0 votes
Least Number of Comparisons will be $4$ if the Numbers are already sorted and we apply Insertion sort Idea.

1 comment

YA no case is explicitly mentioned for input so  4 should be answer BUT IN KENETH ROSEN WHY THEY SOLVED  USING  (LOG N!) i.e concept of comparision based sorting

. "Find the least number of comparisons needed to sort four elements and devise an algorithm that sorts the see ements using this number of comparisons."

and the solution is " By Theorem 1 in this section, at least pog4!l comparisons are needed. Since log2 24 ~ 4.6, at least five comparisons are required. We can accomplish the sorting with five comparisons as follows. (This is essentially just merge sort, as discussed in Section 5.4.) Call the elements a, b, c, and d. First compare a and b; then compare c and d. Without loss of generality, let us assume that a < b and c < d. (If not, then relabel the elements after these comparisons.) Next we compare a and c (this is our third comparison). Whichever is smaller is the smallest element of the set. Again without loss of generality, suppose a < c. Now we merely need to compare b with both c and d to completely determine the ordering. This takes two more comparisons, giving us the desired five in all."
0
0

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true