3
$\begingroup$

I'm having some trouble solving this thing.

You're given an unlimited number of "black boxes" which will return the maximum or the minimum between 2 inputs.

The goal is to compare/sort 4 numbers using those boxes. It is pretty easy to find the smallest and the largest, but I can't seem to figure out how to identify the 2 middle numbers. Any tips?

$\endgroup$
  • $\begingroup$ What does it mean that the "black boxes" can get you the maximum or the minimum? Do you put two inputs into a box, and the box decides whether it gives you max or min? And does the box tell you whether it is giving you max, or the min? $\endgroup$ – Gamow Apr 9 '16 at 17:23
  • $\begingroup$ These are 2 types of boxes to use, both of them are "fed" with 2 inputs (numbers), one of them outputs the minimum between the 2 inputs and the other gets you the maximum between the 2 inputs. you may use as many "black boxes" as you need $\endgroup$ – user3921 Apr 9 '16 at 17:25
  • 2
    $\begingroup$ You aren't trying to optimize the number of boxes, so any sorting network will work (each switch is just composed of one min box and one max box). $\endgroup$ – Erick Wong Apr 9 '16 at 17:29
  • $\begingroup$ This sounds a lot like an algorithms homework assignment. $\endgroup$ – Ian MacDonald Apr 11 '16 at 16:06
2
$\begingroup$

E = MAX(A, B)
F = MAX(C, D)
G = MIN(E, F)

H = MIN(A, B)
I = MIN(C, D)
J = MAX(H, I)

Now G and J are the middle ones.

K = MAX(G, J)
L = MIN(G, J)

K is second, L is third.

$\endgroup$
2
$\begingroup$

Use three boxes to find the minimum element of the four.

Use two boxes to find the minimum element of the remaining three.

Use one box to find the minimum element of the remaining two.

$\endgroup$
  • $\begingroup$ I think there's no operation available to define "the remaining n". The results of the boxes are only ever values, not "which value". $\endgroup$ – KeyboardWielder Apr 10 '16 at 15:27
0
$\begingroup$

Algorithms, which limit themselves by this are called Sorting networks. You can read the wiki to learn more. Solution to your problem would be to compare and find max&min in the following pairs:

1-2, 3-4, 1-3, 2-4, 2-3

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.