SELF DOUBT DM ROSEN

Question

Find the least number of comparisons needed to sort five element.

 

I AM GETTING 7 AS (LOG 5!) =7........

Answer 1

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

Comments

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."