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?

Improve this question
$\endgroup$
4
  • $\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, 2016 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, 2016 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, 2016 at 17:29
  • $\begingroup$ This sounds a lot like an algorithms homework assignment. $\endgroup$
    – Ian MacDonald
    Apr 11, 2016 at 16:06

3 Answers 3

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\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, 2016 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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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