1 votes 1 votes There exists a comparison sort of 5 numbers that uses at most 6 comparisons in the worst case. True or False and Why? Algorithms algorithms sorting true-false + – Rishav Kumar Singh asked Jul 29, 2018 retagged Aug 28, 2022 by Shubham Sharma 2 Rishav Kumar Singh 282 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes False. The number of leaves of a decision tree which sorts 5 numbers is 5! and the height of the tree is at least lg(5!). Since 5! = 120, 2^6 = 64, and 2^7 = 128, we have 6 < lg(5!) < 7. Thus at least 7 comparisons are required. rsansiya111 answered Aug 27, 2022 rsansiya111 comment Share Follow See 1 comment See all 1 1 comment reply rsansiya111 commented Aug 27, 2022 reply Follow Share https://ocw.mit.edu/courses/6-046j-introduction-to-algorithms-sma-5503-fall-2005/f0cdfd373e9f8b7c839e7ed13bbfe748_quiz1_sol.pdf 0 votes 0 votes Please log in or register to add a comment.