This appears a simple problem: given numbers a, b, c, d, e, swap them around so as to place the median in c and partition the others around it. I.e. the postcondition is: a <= c && b <= c && c <= d && c <= e.

Searching the Net for this isn't easy. Fortunately "our own" Xinok has the best of breed result, see http://stackoverflow.com/questions/11065963/possible-to-partition-five-elements-by-median-with-six-comparisons.

His algorithm is a little suboptimal in that when given a sorted array, it sometimes leaves it unsorted. So I changed it to http://dpaste.dzfl.pl/5fb2238d9891 to fix that. If I count right, it also saves one swap: does 0-9 swaps instead of 0-10.

Ideally however, such an algorithm would do 0 swaps if the median is already in c. My algorithm may still swap d and e without necessity.

So there's got to be a better solution. Your challenge - should you choose to accept it :o) - is an algorithm that does the partitioning in 6 comparisons and <= 9 swaps, which is idempotent: when applied twice, it always does 0 swaps.


Andrei

On Thursday, 4 February 2016 at 01:24:15 UTC, Andrei Alexandrescu wrote:
> This appears a simple problem: given numbers a, b, c, d, e, swap them around so as to place the median in c and partition the others around it. I.e. the postcondition is: a <= c && b <= c && c <= d && c <= e.
>
> <snip>
>
> So there's got to be a better solution. Your challenge - should you choose to accept it :o) - is an algorithm that does the partitioning in 6 comparisons and <= 9 swaps, which is idempotent: when applied twice, it always does 0 swaps.

 Well if we look at it, the max compares for optimal sorting algorithm is the log2 of the max combinations in how the elements could be arranged; !5 = 120 or 7 compares.

 I'm not sure of the max swaps, seems like it could be 4 if done right, but that might be impractical.

On Thursday, 4 February 2016 at 01:33:54 UTC, Era Scarecrow wrote:
> On Thursday, 4 February 2016 at 01:24:15 UTC, Andrei Alexandrescu wrote:
>> This appears a simple problem: given numbers a, b, c, d, e, swap them around so as to place the median in c and partition the others around it. I.e. the postcondition is: a <= c && b <= c && c <= d && c <= e.
>>
>> <snip>
>>
>> So there's got to be a better solution. Your challenge - should you choose to accept it :o) - is an algorithm that does the partitioning in 6 comparisons and <= 9 swaps, which is idempotent: when applied twice, it always does 0 swaps.
>
>  Well if we look at it, the max compares for optimal sorting algorithm is the log2 of the max combinations in how the elements could be arranged; !5 = 120 or 7 compares.

The order of a,b and d,e don't matter because we're partitioning, not sorting. So this problem can be solved in six comparisons.

>  I'm not sure of the max swaps, seems like it could be 4 if done right, but that might be impractical.

I believe that's correct. Each swap can move at least one element into it's final position. After three swaps, there may be two elements which are still out of place, and swapping them will move them both into their final position. Thus, four swaps max. :-)


A solution to this problem does exist: Build a tree of if-else branches for all the different possibilities (2^6=64) and hard-code the optimal sequence of swaps. However, this function would be huge so this isn't very practical. Ideally, we want to minimize the size of the function as much as possible, adding in a few extra swaps if necessary.

I'll take a crack at it this weekend. It sounds like an interesting problem.

On 02/03/2016 09:46 PM, Xinok wrote:
> I'll take a crack at it this weekend. It sounds like an interesting
> problem.

Thanks very much! -- Andrei

On Thursday, 4 February 2016 at 02:46:42 UTC, Xinok wrote:
> A solution to this problem does exist: Build a tree of if-else branches for all the different possibilities (2^6=64) and hard-code the optimal sequence of swaps. However, this function would be huge so this isn't very practical.

 Yeah that's kinda what i was coming to a conclusion to.

> Ideally, we want to minimize the size of the function as much as possible, adding in a few extra swaps if necessary.

 Hmmm if i wrote it (this way) it would probably brute force the proper way to build the function rather than doing it by hand myself. So a helper function to make the optimal if/else statements to deal with it.

 BUT this only makes sense if it's always going to be 5 elements, if it's fewer or more, then it's sorta pointless and a more generic algorithm would be preferred.

 Although writing a brute force program creation helper function could still be of some use.

On 02/04/2016 03:46 AM, Xinok wrote:
>
>>  I'm not sure of the max swaps, seems like it could be 4 if done
>> right, but that might be impractical.
>
> I believe that's correct. Each swap can move at least one element into
> it's final position. After three swaps, there may be two elements which
> are still out of place, and swapping them will move them both into their
> final position. Thus, four swaps max. :-)

Three swaps are always enough. Using the first swap, put the median where it belongs, and each subsequent swap can be chosen such that it moves two elements to their final position.

On 02/04/2016 02:24 AM, Andrei Alexandrescu wrote:
> This appears a simple problem: given numbers a, b, c, d, e, swap them
> around so as to place the median in c and partition the others around
> it. I.e. the postcondition is: a <= c && b <= c && c <= d && c <= e.
>
> Searching the Net for this isn't easy. Fortunately "our own" Xinok has
> the best of breed result, see
> http://stackoverflow.com/questions/11065963/possible-to-partition-five-elements-by-median-with-six-comparisons.
>
>
> His algorithm is a little suboptimal in that when given a sorted array,
> it sometimes leaves it unsorted. So I changed it to
> http://dpaste.dzfl.pl/5fb2238d9891 to fix that. If I count right, it
> also saves one swap: does 0-9 swaps instead of 0-10.
>
> Ideally however, such an algorithm would do 0 swaps if the median is
> already in c. My algorithm may still swap d and e without necessity.
>
> So there's got to be a better solution. Your challenge - should you
> choose to accept it :o) - is an algorithm that does the partitioning in
> 6 comparisons and <= 9 swaps, which is idempotent: when applied twice,
> it always does 0 swaps.
>
>
> Andrei
>

At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):

void partition5(ref int[5] a){
  if(a[0]<a[1]){
    if(a[2]<a[3]){
      if(a[0]<a[2]){
        if(a[1]<a[4]){
          if(a[1]<a[2]){
            if(!(a[2]<a[4])){
              swap(a[4],a[2]);
            }
          }else if(a[1]<a[3]){
            swap(a[1],a[2]);
          }else{
            swap(a[3],a[2]);
            swap(a[1],a[3]);
          }
        }else if(a[2]<a[4]){
          if(a[3]<a[4]){
            swap(a[3],a[2]);
            swap(a[1],a[3]);
          }else{
            swap(a[4],a[2]);
            swap(a[1],a[4]);
          }
        }else if(a[1]<a[2]){
          swap(a[1],a[2]);
          swap(a[1],a[4]);
        }else{
          swap(a[1],a[4]);
        }
      }else if(a[3]<a[4]){
        if(a[0]<a[3]){
          if(a[1]<a[3]){
            swap(a[1],a[2]);
          }else{
            swap(a[3],a[2]);
            swap(a[1],a[3]);
          }
        }else if(a[0]<a[4]){
          swap(a[0],a[2]);
          swap(a[1],a[3]);
        }else{
          swap(a[4],a[2]);
          swap(a[0],a[3]);
          swap(a[1],a[4]);
        }
      }else if(a[0]<a[4]){
        if(a[1]<a[4]){
          swap(a[1],a[2]);
        }else{
          swap(a[4],a[2]);
          swap(a[1],a[4]);
        }
      }else if(a[0]<a[3]){
        swap(a[0],a[2]);
        swap(a[1],a[4]);
      }else{
        swap(a[3],a[2]);
        swap(a[0],a[3]);
        swap(a[1],a[4]);
      }
    }else if(a[0]<a[3]){
      if(a[1]<a[4]){
        if(a[1]<a[3]){
          if(a[3]<a[4]){
            swap(a[3],a[2]);
          }else{
            swap(a[4],a[2]);
          }
        }else if(a[1]<a[2]){
          swap(a[1],a[2]);
          swap(a[1],a[3]);
        }else{
          swap(a[1],a[3]);
        }
      }else if(a[3]<a[4]){
        if(a[2]<a[4]){
          swap(a[1],a[3]);
        }else{
          swap(a[4],a[2]);
          swap(a[1],a[3]);
        }
      }else if(a[1]<a[3]){
        swap(a[1],a[2]);
        swap(a[1],a[4]);
      }else{
        swap(a[3],a[2]);
        swap(a[1],a[4]);
      }
    }else if(a[2]<a[4]){
      if(a[0]<a[2]){
        if(a[1]<a[2]){
          swap(a[1],a[2]);
          swap(a[1],a[3]);
        }else{
          swap(a[1],a[3]);
        }
      }else if(a[0]<a[4]){
        swap(a[0],a[2]);
        swap(a[1],a[3]);
      }else{
        swap(a[4],a[2]);
        swap(a[0],a[3]);
        swap(a[1],a[4]);
      }
    }else if(a[0]<a[4]){
      if(a[1]<a[4]){
        swap(a[1],a[2]);
        swap(a[1],a[3]);
      }else{
        swap(a[4],a[2]);
        swap(a[1],a[3]);
      }
    }else if(a[0]<a[2]){
      swap(a[0],a[2]);
      swap(a[0],a[3]);
      swap(a[1],a[4]);
    }else{
      swap(a[0],a[3]);
      swap(a[1],a[4]);
    }
  }else if(a[2]<a[3]){
    if(a[0]<a[3]){
      if(a[2]<a[4]){
        if(a[0]<a[4]){
          if(!(a[0]<a[2])){
            swap(a[0],a[2]);
          }
        }else if(a[1]<a[4]){
          swap(a[4],a[2]);
          swap(a[0],a[4]);
        }else{
          swap(a[1],a[2]);
          swap(a[0],a[4]);
        }
      }else if(a[0]<a[2]){
        if(a[0]<a[4]){
          swap(a[4],a[2]);
        }else{
          swap(a[0],a[2]);
          swap(a[0],a[4]);
        }
      }else if(a[1]<a[2]){
        swap(a[0],a[4]);
      }else{
        swap(a[1],a[2]);
        swap(a[0],a[4]);
      }
    }else if(a[1]<a[4]){
      if(a[3]<a[4]){
        if(a[1]<a[3]){
          swap(a[3],a[2]);
          swap(a[0],a[3]);
        }else{
          swap(a[1],a[2]);
          swap(a[0],a[3]);
        }
      }else if(a[2]<a[4]){
        swap(a[4],a[2]);
        swap(a[0],a[4]);
      }else{
        swap(a[0],a[4]);
      }
    }else if(a[1]<a[3]){
      if(a[1]<a[2]){
        swap(a[0],a[4]);
      }else{
        swap(a[1],a[2]);
        swap(a[0],a[4]);
      }
    }else if(a[3]<a[4]){
      swap(a[4],a[2]);
      swap(a[0],a[3]);
      swap(a[1],a[4]);
    }else{swap(a[3],a[2]);
      swap(a[0],a[3]);
      swap(a[1],a[4]);
    }
  }else if(a[0]<a[2]){
    if(a[3]<a[4]){
      if(a[0]<a[4]){
        if(a[0]<a[3]){
          swap(a[3],a[2]);
        }else{
          swap(a[0],a[2]);
          swap(a[0],a[3]);
        }
      }else if(a[1]<a[4]){
        swap(a[4],a[2]);
        swap(a[0],a[3]);
      }else{
        swap(a[1],a[2]);
        swap(a[0],a[3]);
        swap(a[1],a[4]);
      }
    }else if(a[0]<a[3]){
      if(a[0]<a[4]){
        swap(a[4],a[2]);
      }else{
        swap(a[0],a[2]);
        swap(a[0],a[4]);
      }
    }else if(a[1]<a[3]){
      swap(a[3],a[2]);
      swap(a[0],a[4]);
    }else{
      swap(a[1],a[2]);
      swap(a[0],a[3]);
      swap(a[1],a[4]);
    }
  }else if(a[1]<a[4]){
    if(a[2]<a[4]){
      if(a[1]<a[2]){
        swap(a[0],a[3]);
      }else{
        swap(a[1],a[2]);
        swap(a[0],a[3]);
      }
    }else if(a[3]<a[4]){
      swap(a[4],a[2]);
      swap(a[0],a[3]);
    }else{
      swap(a[3],a[2]);
      swap(a[0],a[4]);
    }
  }else if(a[1]<a[2]){
    if(a[1]<a[3]){
      swap(a[3],a[2]);
      swap(a[0],a[4]);
    }else{
      swap(a[1],a[2]);
      swap(a[0],a[3]);
      swap(a[1],a[4]);
    }
  }else if(a[2]<a[4]){
    swap(a[4],a[2]);
    swap(a[0],a[3]);
    swap(a[1],a[4]);
  }else{
    swap(a[0],a[3]);
    swap(a[1],a[4]);
  }
}

On Thursday, 4 February 2016 at 20:30:57 UTC, Timon Gehr wrote:
> At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):
>
> void partition5(ref int[5] a){
>   if(a[0]<a[1]){
>     if(a[2]<a[3]){
>       if(a[0]<a[2]){
>         if(a[1]<a[4]){
>           if(a[1]<a[2]){
>             if(!(a[2]<a[4])){
>               swap(a[4],a[2]);
>             }
>           }else if(a[1]<a[3]){
>             swap(a[1],a[2]);
>           }else{
>             swap(a[3],a[2]);
>             swap(a[1],a[3]);
> <snip>

 That's about what i expected for the actual function (like this) to look like. Course the only way to test this is to brute force the combinations and confirm it's all in the order they should be.

On Thursday, 4 February 2016 at 20:30:57 UTC, Timon Gehr wrote:
> At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):
>
> void partition5(ref int[5] a){
>   if(a[0]<a[1]){
> ...

Great, we can all go home!

I was curious so I did a crude measurement: when compiled for 64-bit with all optimizations turned on (-release -O -inline -boundscheck=off), the machine code for this function is about 3KB in size.

On Thursday, 4 February 2016 at 01:24:15 UTC, Andrei Alexandrescu wrote:
> So there's got to be a better solution. Your challenge - should you choose to accept it :o) - is an algorithm that does the partitioning in 6 comparisons and <= 9 swaps, which is idempotent: when applied twice, it always does 0 swaps.

Here's my take at it.

It's idempotent and does exactly 6 comparisons and 0-8 swaps.
The advantages to counter the not-so-good stats are that it has a flat structure, and is not hard to reason about.

The idea is to process the following steps:

1. Find the minimum of {b, c, d, e} in three comparisons, and put it into b.
The structure is: b < d, c < e, b < c.
Note that d and e were not compared if no swaps were made.

2. Find the minimum of {a, c, d, e} in two more comparisons, and put it into a.
The structure is: a < d, c < e, a < c.
Note that a and b were not compared if no swaps were made.

3. Find the minimum of {c, d, e} in one more comparison, and put it into c.
The structure is: c < d, c < e.
Note that d and e were not compared if no swaps were made.

In the end, we have a < c, b < c, c < d, c < e.
Additionally, if these inequalities held initially, everything is left in place regardless of the results of comparisons of (a, b) and (d, e).

In code:
-----
import std.algorithm;
import std.exception;
import std.range;
import std.stdio;

void p5 (ref int a, ref int b, ref int c, ref int d, ref int e)
{
    if (d < b) {swap (b, d);}
    if (e < c) {swap (c, e);}
    if (c < b) {swap (b, c); swap (d, e);}
    if (d < a) {swap (a, d);}
    if (c < a) {swap (a, c); swap (d, e);}
    if (d < c) {swap (c, d);}
}

void main ()
{
    auto a = 5.iota.array;
    do
    {
        auto b = a.dup;
        p5 (b[0], b[1], b[2], b[3], b[4]);
        auto c = b.dup;
        p5 (c[0], c[1], c[2], c[3], c[4]);
        writeln (a, " -> ", b, " -> ", c);
        enforce (b[0] < b[2] && b[1] < b[2] &&
            b[2] < b[3] && b[2] < b[4]);
        enforce (equal (b, c));
    }
    while (nextPermutation (a));
}
-----

Another interesting task would be to make the function stable, but I don't see how it is possible with such flat structure.

Ivan Kazmenko.