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]);
}
}
