Idempotent partition around median of 5?

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Thu Feb 4 12:30:57 PST 2016


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



More information about the Digitalmars-d mailing list