http://www.waytocrack.com/forum/index.php/387/minimum-number-sort5-functions-get-top-five-elements-array?show=388
Suppose you are given a set S of 25 distinct integers and a CPU that has a special instruction, SORT5, that can sort five integers in one cycle. Your task is to identify the largest, second-largest, and third-largest integers in S using SORT5 to compare and sort subsets of S; furthermore, you must minimize the number of calls to SORT5.
Races 1-5: Group the 25 horses into 5 groups of 5, and race them to find out the order of horses within each group.
This allows us to create a grid as follows (labelling the horses A-Y):
Race 1: ABCDE
Race 2: FGHIJ
Race 3: KLMNO
Race 4: PQRST
Race 5: UVWXY
In case that's difficult to understand, take Race 1 for an example. What the grid shows is that horse A came in 1st, horse B 2nd, horse C 3rd, horse D 4th and horse E 5th. So horse P won race 4, for instance.
Race 6: Race all 5 winners (A, F, K, P, U). Let's assume horse A won the race, F finished 2nd, K finished 3rd, P finished 4th and U finished last (just because it's easy to order).
This tells us that horse A is the fastest horse.
It also tells us that horse V,W,X,Y cannot be in the top 5, because they are slower than U, which is slower than A,F,K and P. Similarly, R,S,T cannot be in the top 5 (slower than A,F,K,P and Q), N,O cannot be in the top 5 (slower than A,F,K,L,M) and J cannot be in the top 5 (slower than A,F,G,H,I). Replacing all horses that are ruled out with #, we get:
ABCDE
FGHI#
KLM##
PQ###
U####
Race 7: We want to find out the 2nd and 3rd fastest horses, so we race all the possible candidates. These can only be B,C,F,G,K (since every other horse is slower than at least 3 horses).
You can work through the possible scenarios, but they will all allow us to eliminate 8 horses. We can illustrate an example: assume it finished F first, B second, K third, G fourth, C fifth.
We thus know that the top 3 horses are (in order) A,F,B.
We can also eliminate other horses from consideration. C cannot be in the top 5, since it is slower than A,F,B,K and G, hence any horse slower than C is also out of the picture (D,E). Similarly, H,I cannot be in the top 5 (slower than A,F,B,K,G), M cannot be in the top 5 (slower than A,F,B,K,L), and Q and U cannot be in the top 5 (slower than A,F,B,K,P). This leaves us with:
AB###
FG###
KL###
P####
#####
Race 8: Just race the remaining horses with the 3rd horse (B,G,K,L,P) and you'll know which are the 4th and 5th horses.
This allows us to create a grid as follows (labelling the horses A-Y):
Race 1: ABCDE
Race 2: FGHIJ
Race 3: KLMNO
Race 4: PQRST
Race 5: UVWXY
In case that's difficult to understand, take Race 1 for an example. What the grid shows is that horse A came in 1st, horse B 2nd, horse C 3rd, horse D 4th and horse E 5th. So horse P won race 4, for instance.
Race 6: Race all 5 winners (A, F, K, P, U). Let's assume horse A won the race, F finished 2nd, K finished 3rd, P finished 4th and U finished last (just because it's easy to order).
This tells us that horse A is the fastest horse.
It also tells us that horse V,W,X,Y cannot be in the top 5, because they are slower than U, which is slower than A,F,K and P. Similarly, R,S,T cannot be in the top 5 (slower than A,F,K,P and Q), N,O cannot be in the top 5 (slower than A,F,K,L,M) and J cannot be in the top 5 (slower than A,F,G,H,I). Replacing all horses that are ruled out with #, we get:
ABCDE
FGHI#
KLM##
PQ###
U####
Race 7: We want to find out the 2nd and 3rd fastest horses, so we race all the possible candidates. These can only be B,C,F,G,K (since every other horse is slower than at least 3 horses).
You can work through the possible scenarios, but they will all allow us to eliminate 8 horses. We can illustrate an example: assume it finished F first, B second, K third, G fourth, C fifth.
We thus know that the top 3 horses are (in order) A,F,B.
We can also eliminate other horses from consideration. C cannot be in the top 5, since it is slower than A,F,B,K and G, hence any horse slower than C is also out of the picture (D,E). Similarly, H,I cannot be in the top 5 (slower than A,F,B,K,G), M cannot be in the top 5 (slower than A,F,B,K,L), and Q and U cannot be in the top 5 (slower than A,F,B,K,P). This leaves us with:
AB###
FG###
KL###
P####
#####
Race 8: Just race the remaining horses with the 3rd horse (B,G,K,L,P) and you'll know which are the 4th and 5th horses.
In case analysis, a problem is divided into a number of separate cases, and analyzing each such case individually suffices to solve the initial problem. Cases do not have to be mutually exclusive; however, they must be exhaustive, that is cover all possibilities.
However, if you do a careful case analysis and eliminate all x ∈ S for which there are at least three integers in S larger than x, only five integers remain and hence just one more call to SORT5 is needed to compute the result.
