SORT5
Last updated
Last updated
Suppose you are given 25 distinct integers and a function, SORT5, that can sort five integers at a time. Compute the largest, second-largest, and third-largest integers among those 25 integers using SORT5 function and minimize the number of calls to SORT5.
Reference: EPI python, page 200
Idea: (6 sorting in total)
Split the 25 integers into 5 groups randomly, each group has 5 integers.
Sort 5 groups individually.
let be the largest integer in each group, sort these 5 integers. Suppose we have . Then is the largest integer.
To get the second largest integer, is a candidate, and second largest value in the 1st group is another candidate.
To get the third largest integer, are candidates, second largest value in the 1st group , third largest value in the 1st group , and second largest integer in the second group are also candidates. Thus we need to sort to get the second largest and third largest.