Chapter 4 Case Analysis SORT5 problem explanation

#1

I think the problem solution explanation for the SORT5 problem isnt clear enough. I came up with a solution which entails 8 uses of SORT5 and am not sure if this is the most optimised solution. I believe in a future version of the book you should explain the ideal solution a bit more clearly.

I believe the same applies for the Boyer Moore explanation in the Iterative Refinement of a Brute-Force section of the same chapter

My clearer explanation of the SORT5 solution for other people below : -

Use SORT5 to extract the highest (h1), second highest (h2) and third highest (h3) numbers for subsets S1 to S5 and then do individual SORT5 for the H1, H2 and H3 subsets of the highest, second highest and third highest. If there is a better solution please explain below.

0 Likes
#2

Hey @apro,

Sorry that we did not explain that very well, and we recently decide to remove the problems in Chapter 4 and then move those problems into each corresponding chapter for better explanation.

Following is our new and detailed solution for this problem:

If all we had to compute was the largest integer in the set, the optimum approach would be to form five disjoint subsets S1, . . . , S5 of the input, sort each subset, and then sort {max S1 , . . . , max S5 }. This takes six calls to SORT5 but leaves ambiguity about the second and third largest integers. We could repeat the process to find the second and third largest integers, but this approach does not take advantage of already performed computations.
Let m1, m2, m3, m4, m5 be the largest values in S1 , . . . , S5 , and suppose without loss of generality that m1 > m2 > m3 > m4 > m5. Then m4 and m5 cannot possibly be the second or third largest values, and neither can any other value in S4 and S5. Similarly, from S3, nothing other than m3 can be the third smallest value, and from S2, only m2 and the next largest number in S2 (call it b2) can be the second or third smallest numbers. From S1 only the next two largest numbers (call them a1 and a2) can be the second or third smallest numbers. Therefore the second and third largest numbers must be from a1, a2, m2, b2, m3, and we can determine them with one additional call to SORT5.

Please feel free to let me know if you have any other question.

0 Likes
#3

Thanks for the explanation, its much clearer now.

0 Likes