10
$\begingroup$

Min-Max is a box that is capable of determining which of the two numbers is the higher (Max) and which is lower (Min).

enter image description here

I need to use minimum amount of boxes in order to sort 4 different numbers (any A, B, C, D). For example:

enter image description here

| improve this question | |
$\endgroup$
18
$\begingroup$

You need at least

five boxes,

as each box makes a binary choice (factor of 2), and you have 24 possible orders for the relative values of 4 numbers. See below for an example of a 'minimal' box solution.

enter image description here

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Here's a relevant wiki link: Sorting network $\endgroup$ – Jaap Scherphuis Jun 26 '19 at 8:15
  • 1
    $\begingroup$ @IanMacDonald (1) Even if results were deterministic, sports playoffs often don't get even the 2nd placed team right, since there's a very high possibility that the 2nd best team starts from the same side of the draw as the best team. (2) And because game results aren't deterministic, some sorting networks could be very unfair for some spots in the draw. $\endgroup$ – JiK Jun 26 '19 at 15:57
  • 1
    $\begingroup$ @IanMacDonald I was probably a bit unclear in my attempt to be constructive and polite. What I mean is: No sports playoff system is a sorting network, not even ones where the losers don't go home but keep on playing for lower positions. The two are not related at all. Your comment "also known as sports playoffs" is completely wrong and demonstrates you have probably either not understood sports playoffs or not understood sorting networks. $\endgroup$ – JiK Jun 26 '19 at 19:41
  • 1
    $\begingroup$ Or, more precisely: No actually used sports playoff system is a sorting network. And just taking a sorting network would probably give a very unbalanced sports playoff system so it won't be used. $\endgroup$ – JiK Jun 26 '19 at 19:54
  • 1
    $\begingroup$ @IanMacDonald You might be confusing sorting networks with just general comparator networks. A sorting network is required to give the correct ordering at the end, no matter the input, not just any ordering. If you convert the usual single-elimination sports playoff system into a comparator network, that does give the correct 1st element but not necessarily the correct 2nd element. $\endgroup$ – JiK Jun 27 '19 at 13:25
1
$\begingroup$

The worst-case situation is when the greatest number is at the bottom and/or the least one is at the top, so it/they need(s) to be shifted the farthest.

So you need at least:

three boxes to shift such a number to the opposite side,

and therefore:

five boxes are required in total;

like this (for example):

A - - +-----+ - - - - - - - - +-----+ - - greatest
      |     |                 |     |
B - - +-----+ - - +-----+ - - +-----+ - - ...
                  |     |
C - - +-----+ - - +-----+ - - +-----+ - - ...
      |     |                 |     |
D - - +-----+ - - - - - - - - +-----+ - - least

For $n$ numbers you need:

$2*n-3$ boxes in total, arranged in the above illustrated $X$-shape.

Like this for $n=5$: 

A - - +-----+ - - - - - - - - - - - - - - - - - - - - +-----+ - - greatest
      |     |                                         |     |
B - - +-----+ - - +-----+ - - - - - - - - +-----+ - - +-----+ - - ...
                  |     |                 |     |
C - - - - - - - - +-----+ - - +-----+ - - +-----+ - - - - - - - - ...
                              |     |
D - - +-----+ - - - - - - - - +-----+ - - - - - - - - +-----+ - - ...
      |     |                                         |     |
E - - +-----+ - - - - - - - - - - - - - - - - - - - - +-----+ - - least
and this for $n=6$: 
A - - +-----+ - - - - - - - - - - - - - - - - - - - - +-----+ - - greatest
      |     |                                         |     |
B - - +-----+ - - +-----+ - - - - - - - - +-----+ - - +-----+ - - ...
                  |     |                 |     |
C - - - - - - - - +-----+ - - +-----+ - - +-----+ - - - - - - - - ...
                              |     |
D - - - - - - - - +-----+ - - +-----+ - - +-----+ - - - - - - - - ...
                  |     |                 |     |
E - - +-----+ - - +-----+ - - - - - - - - +-----+ - - +-----+ - - ...
      |     |                                         |     |
F - - +-----+ - - - - - - - - - - - - - - - - - - - - +-----+ - - least
As you can see, if the top number needs to be shifted to the bottom, it needs to pass through $n-1$ boxes; the same is true for shifting the bottom number to the top; the centre box is shared for both directions, so we get $(n-1)+(n-1)-1$ boxes.

| improve this answer | |
$\endgroup$
  • $\begingroup$ While you prove a lower bound, it does not mean that the lower bound can be attained. Even if it can be attained, the cross shaped arrangement will not be a sorting network for the middle elements. For example, your $n=4$ network with five boxes will not sort $4321$, as it transforms this to $3412$ then $3142$, and finally $1324$. There is only one box that exchanges an element from the top/first half to the bottom/second half, so it will never be able to sort the reversed sequence for $n\ge4$. $\endgroup$ – Jaap Scherphuis Jun 27 '19 at 11:18
  • $\begingroup$ Actually, the lower bound that you prove is only valid if you are restricted to adjacent swaps. If you allow non-adjacent swaps, then the argument does not work because you could exchange the first and last elements with a single box instead of $2n-3$. There is no such restriction imposed in this question. $\endgroup$ – Jaap Scherphuis Jun 27 '19 at 11:38
  • $\begingroup$ Actually, this problem is open problem in general. $\endgroup$ – Xwtek Jul 17 '19 at 0:34

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.