img/home.png

Sorts on the Edge


People often believe, that Quicksort is the ultimate sort. That there is no possible way to sort faster than Quick does. Some do know however, that it may be so for the so called logical sorts, but not for the so called mathematical sorts, which do more than a logical compare and a switch when appropriate. Exploiting counting, Radix (and even better Postman's) sort, can both be faster than Quicksort. Not always, but for an important part of possible cases, they are both faster.

Let us focus on logical sorts for now! For some special cases, we can outperform Quicksort, too! One known niche is sorting small arrays with so called comparators, invented by Knuth, Green and others. Knowing that only a fixed (say 16) members are to be sorted, 60 fixed COMPEX (COMpare and EXchange) operations are always enough to sort those 16 numbers. It's quicker than Quicksort.

Daniel Hillis even tried to evolve a 16 records comparator and was able to get a 61 COMPEX long algorithm. One more, than the best known - Green's.

Those comparators are faster than Qiucksort. They harness the information of how many elements to expect, when Quicksort is a general algorithm, suitable for any array size.

Green's algorithm:

COMPEX(a[0],a[1])  
COMPEX(a[2],a[3])  
COMPEX(a[4],a[5])  
COMPEX(a[6],a[7])  
COMPEX(a[8],a[9])  
COMPEX(a[10],a[11])  
COMPEX(a[12],a[13])  
COMPEX(a[14],a[15])  
COMPEX(a[1],a[3])  
COMPEX(a[5],a[7])  
COMPEX(a[9],a[11])  
COMPEX(a[13],a[15])  
COMPEX(a[0],a[2])  
COMPEX(a[4],a[6])  
COMPEX(a[8],a[10])  
COMPEX(a[12],a[14])  
COMPEX(a[3],a[7])  
COMPEX(a[11],a[15])  
COMPEX(a[2],a[6])  
COMPEX(a[10],a[14])  
COMPEX(a[1],a[5])  
COMPEX(a[9],a[13])  
COMPEX(a[0],a[4])  
COMPEX(a[8],a[12])  
COMPEX(a[7],a[15])  
COMPEX(a[6],a[14])  
COMPEX(a[5],a[13])  
COMPEX(a[4],a[12])  
COMPEX(a[3],a[11])  
COMPEX(a[2],a[10])  
COMPEX(a[1],a[9])  
COMPEX(a[0],a[8])  
COMPEX(a[5],a[10])  
COMPEX(a[6],a[9])  
COMPEX(a[1],a[2])  
COMPEX(a[3],a[12])  
COMPEX(a[4],a[8])  
COMPEX(a[7],a[11])  
COMPEX(a[13],a[14])  
COMPEX(a[2],a[8])  
COMPEX(a[11],a[14])  
COMPEX(a[1],a[4])  
COMPEX(a[7],a[13])  
COMPEX(a[2],a[4])  
COMPEX(a[5],a[6])  
COMPEX(a[9],a[10])  
COMPEX(a[11],a[13])  
COMPEX(a[7],a[12])  
COMPEX(a[3],a[8])  
COMPEX(a[3],a[5])  
COMPEX(a[7],a[9])  
COMPEX(a[6],a[8])  
COMPEX(a[10],a[12])  
COMPEX(a[3],a[4])  
COMPEX(a[5],a[6])  
COMPEX(a[7],a[8])  
COMPEX(a[9],a[10])  
COMPEX(a[11],a[12])  
COMPEX(a[6],a[7])  

You may wonder, if Critticall is able to improve it further? As a matter in fact - it is! By decomposing COMPEX to COMP and EX. Doing more COMPares and less EXchanges. You can try this by yourself and see, that for instance once you know that a[0] is greater then a[1], it may be wise to compare it with a[7], be cause the probability that a[0] is above average is more than 50%. Try to put it further than to the second place now, when this information is present! This kind of improvements have arisen so far. Stunned already?

Those improvements you will see in minutes, but for a greater reduction (for example to a hypothetical 59 COMPEX), you may need to wait for days. Nobody knows, if less than 60 comparators are enough. Maybe it's worth to try? Here is the template (Green's algorithm in Critticall language, waiting to be optimized):


$declareint temp n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 n10 n11 n12 n13 n14 n15
$dimension a[16]
$rinvar a[](0,31)
$retvar a[]
$rescom while var_to_array array_to_var operation val_operation function inc_dec val_to_var break
$randomize timer

n0=0;n1=1;n2=2;n3=3;n4=4;n5=5;n6=6;n7=7;n8=8;n9=9;n10=10;n11=11;n12=12;n13=13;n14=14;n15=15;

if (a[n0]>a[n1])   {temp=a[n0]; a[n0]=a[n1]; a[n1]=temp;}
if (a[n2]>a[n3])   {temp=a[n2]; a[n2]=a[n3]; a[n3]=temp;}
if (a[n4]>a[n5])   {temp=a[n4]; a[n4]=a[n5]; a[n5]=temp;}
if (a[n6]>a[n7])   {temp=a[n6]; a[n6]=a[n7]; a[n7]=temp;}
if (a[n8]>a[n9])   {temp=a[n8]; a[n8]=a[n9]; a[n9]=temp;}
if (a[n10]>a[n11]) {temp=a[n10]; a[n10]=a[n11]; a[n11]=temp;}
if (a[n12]>a[n13]) {temp=a[n12]; a[n12]=a[n13]; a[n13]=temp;}
if (a[n14]>a[n15]) {temp=a[n14]; a[n14]=a[n15]; a[n15]=temp;}
if (a[n1]>a[n3])   {temp=a[n1]; a[n1]=a[n3]; a[n3]=temp;}
if (a[n5]>a[n7])   {temp=a[n5]; a[n5]=a[n7]; a[n7]=temp;}
if (a[n9]>a[n11])  {temp=a[n9]; a[n9]=a[n11]; a[n11]=temp;}
if (a[n13]>a[n15]) {temp=a[n13]; a[n13]=a[n15]; a[n15]=temp;}
if (a[n0]>a[n2])   {temp=a[n0]; a[n0]=a[n2]; a[n2]=temp;}
if (a[n4]>a[n6])   {temp=a[n4]; a[n4]=a[n6]; a[n6]=temp;}
if (a[n8]>a[n10])  {temp=a[n8]; a[n8]=a[n10]; a[n10]=temp;}
if (a[n12]>a[n14]) {temp=a[n12]; a[n12]=a[n14]; a[n14]=temp;}
if (a[n3]>a[n7])   {temp=a[n3]; a[n3]=a[n7]; a[n7]=temp;}
if (a[n11]>a[n15]) {temp=a[n11]; a[n11]=a[n15]; a[n15]=temp;}
if (a[n2]>a[n6])   {temp=a[n2]; a[n2]=a[n6]; a[n6]=temp;}
if (a[n10]>a[n14]) {temp=a[n10]; a[n10]=a[n14]; a[n14]=temp;}
if (a[n1]>a[n5])   {temp=a[n1]; a[n1]=a[n5]; a[n5]=temp;}
if (a[n9]>a[n13])  {temp=a[n9]; a[n9]=a[n13]; a[n13]=temp;}
if (a[n0]>a[n4])   {temp=a[n0]; a[n0]=a[n4]; a[n4]=temp;}
if (a[n8]>a[n12])  {temp=a[n8]; a[n8]=a[n12]; a[n12]=temp;}
if (a[n7]>a[n15])  {temp=a[n7]; a[n7]=a[n15]; a[n15]=temp;}
if (a[n6]>a[n14])  {temp=a[n6]; a[n6]=a[n14]; a[n14]=temp;}
if (a[n5]>a[n13])  {temp=a[n5]; a[n5]=a[n13]; a[n13]=temp;}
if (a[n4]>a[n12])  {temp=a[n4]; a[n4]=a[n12]; a[n12]=temp;}
if (a[n3]>a[n11])  {temp=a[n3]; a[n3]=a[n11]; a[n11]=temp;}
if (a[n2]>a[n10])  {temp=a[n2]; a[n2]=a[n10]; a[n10]=temp;}
if (a[n1]>a[n9])   {temp=a[n1]; a[n1]=a[n9]; a[n9]=temp;}
if (a[n0]>a[n8])   {temp=a[n0]; a[n0]=a[n8]; a[n8]=temp;}
if (a[n5]>a[n10])  {temp=a[n5]; a[n5]=a[n10]; a[n10]=temp;}
if (a[n6]>a[n9])   {temp=a[n6]; a[n6]=a[n9]; a[n9]=temp;}
if (a[n1]>a[n2])   {temp=a[n1]; a[n1]=a[n2]; a[n2]=temp;}
if (a[n3]>a[n12])  {temp=a[n3]; a[n3]=a[n12]; a[n12]=temp;}
if (a[n4]>a[n8])   {temp=a[n4]; a[n4]=a[n8]; a[n8]=temp;}
if (a[n7]>a[n11])  {temp=a[n7]; a[n7]=a[n11]; a[n11]=temp;}
if (a[n13]>a[n14]) {temp=a[n13]; a[n13]=a[n14]; a[n14]=temp;}
if (a[n2]>a[n8])   {temp=a[n2]; a[n2]=a[n8]; a[n8]=temp;}
if (a[n11]>a[n14]) {temp=a[n11]; a[n11]=a[n14]; a[n14]=temp;}
if (a[n1]>a[n4])   {temp=a[n1]; a[n1]=a[n4]; a[n4]=temp;}
if (a[n7]>a[n13])  {temp=a[n7]; a[n7]=a[n13]; a[n13]=temp;}
if (a[n2]>a[n4])   {temp=a[n2]; a[n2]=a[n4]; a[n4]=temp;}
if (a[n5]>a[n6])   {temp=a[n5]; a[n5]=a[n6]; a[n6]=temp;}
if (a[n9]>a[n10])  {temp=a[n9]; a[n9]=a[n10]; a[n10]=temp;}
if (a[n11]>a[n13]) {temp=a[n11]; a[n11]=a[n13]; a[n13]=temp;}
if (a[n7]>a[n12])  {temp=a[n7]; a[n7]=a[n12]; a[n12]=temp;}
if (a[n3]>a[n8])   {temp=a[n3]; a[n3]=a[n8]; a[n8]=temp;}
if (a[n3]>a[n5])   {temp=a[n3]; a[n3]=a[n5]; a[n5]=temp;}
if (a[n7]>a[n9])   {temp=a[n7]; a[n7]=a[n9]; a[n9]=temp;}
if (a[n6]>a[n8])   {temp=a[n6]; a[n6]=a[n8]; a[n8]=temp;}
if (a[n10]>a[n12]) {temp=a[n10]; a[n10]=a[n12]; a[n12]=temp;}
if (a[n3]>a[n4])   {temp=a[n3]; a[n3]=a[n4]; a[n4]=temp;}
if (a[n5]>a[n6])   {temp=a[n5]; a[n5]=a[n6]; a[n6]=temp;}
if (a[n7]>a[n8])   {temp=a[n7]; a[n7]=a[n8]; a[n8]=temp;}
if (a[n9]>a[n10])  {temp=a[n9]; a[n9]=a[n10]; a[n10]=temp;}
if (a[n11]>a[n12]) {temp=a[n11]; a[n11]=a[n12]; a[n12]=temp;}
if (a[n6]>a[n7])   {temp=a[n6]; a[n6]=a[n7]; a[n7]=temp;}
if (a[n8]>a[n9])   {temp=a[n8]; a[n8]=a[n9]; a[n9]=temp;}

But can we do it even better? At least in principle (and already some in practice) we can! Suppose that I know, that the fastest way to sort a and b is to compare (and switch them if a is greater). Then insert c where it fits, as in the following program:

$DECLAREINT a b c temp
$RINVAR a(0,15) b(0,15)  c(0,15)
$RETVAR  a b c
$RESCOM while operation val_operation function inc_dec val_to_var var_to_array array_to_var break goto

if (a>b)  {temp=a;a=b;b=temp;} // sort a and b


if (a>c)  {temp=a;a=c;c=temp;} //
                               // insert c 
if (b>c)  {temp=b;b=c;c=temp;} //
In minutes you may get something like this, where unnecessary moves are reduced.

// The algorithm has been enhanced For 21.5686%

 $DECLAREINT a b temp c 

 $RINVAR a(0,15) b(0,15) c(0,15) 
 $RETVAR  a  b  c 
 $RESCOM while operation val_operation function inc_dec val_to_var var_to_array array_to_var break goto

// int a=0;int b=0;int temp=0;int c=0;

$BES
if (a>c) {
    temp=a;
    a=c;
    c=temp;
}
if (b>c) {
    temp=b;
    b=c;
    c=temp;
} else {
    if (a>b) {
        temp=a;
        a=b;
        b=temp;
    }
}


As you see, the outer records are compared (and switched if need to), then the middle one is compared to just one. In 2/3 of the cases another compare is made, but in either case, just one additional exchange (two in all) is needed.

You may be surprised with what is going to come out from Critticall, chewing this or any bigger list sort, created the same way. Optimizing known (or assumed) optimum sort for N plus inserting (N+1)th record, to a whole new sort story!

Perhaps something like this. Faster than any Quick or comparator based sort.

$DECLAREINT a d c b e critticall2                                                                     
$RINVAR a(0,15) b(0,15) c(0,15) d(0,15) e(0,15)                                                       
$RETVAR  a  b  c  d  e                                                                                
$RESCOM while operation val_operation function inc_dec val_to_var var_to_array array_to_var break goto
                                                                                                       
// int a=0;int d=0;int c=0;int b=0;int e=0;int critticall2=0;                                          
                                                                                                       
if (b>e) {                                                                                             
    critticall2=b;                                                                                     
    b=e;                                                                                               
    e=critticall2;                                                                                     
}                                                                                                      
if (a>d) {                                                                                             
    critticall2=a;                                                                                     
    a=d;                                                                                               
    d=critticall2;                                                                                     
}                                                                                                      
if (a>c) {                                                                                             
    critticall2=a;                                                                                     
    a=c;                                                                                               
    c=critticall2;                                                                                     
}                                                                                                      
if (b>=c) {                                                                                            
    critticall2=b;                                                                                     
    b=c;                                                                                               
    c=critticall2;                                                                                     
} else {                                                                                               
    if (c>e) {                                                                                         
        if (a>e) {                                                                                     
            critticall2=a;                                                                             
            a=e;                                                                                       
            e=critticall2;                                                                             
        }                                                                                              
        critticall2=c;                                                                                 
        c=e;                                                                                           
        e=critticall2;                                                                                 
    }                                                                                                  
    if (a>b) {                                                                                         
        critticall2=a;                                                                                 
        a=b;                                                                                           
        b=critticall2;                                                                                 
    }                                                                                                  
}                                                                                                      
if (d>e) {                                                                                             
    critticall2=d;                                                                                     
    d=e;                                                                                               
    e=critticall2;                                                                                     
} else {                                                                                               
    if (c>d) {                                                                                         
        if (b>d) {                                                                                     
            critticall2=b;                                                                             
            b=d;                                                                                       
            d=critticall2;                                                                             
        }                                                                                              
        critticall2=c;                                                                                 
        c=d;                                                                                           
        d=critticall2;                                                                                 
    }                                                                                                  
}                                                                                                      


It is difficult to understand how exactly it works or what is the point of all those nestings, but (the array version) needs about a half of the steps and a fifth of the time, Quicksort needs. Note however, that with the $weights metacommand, a command's weight may be changed to accommodate your compiler and your computer configuration. The default value is 1 for setting a variable to another variable, and 2 for the if statement. This may be changed in any appropriate way. The result program may be quite different, optimized for the particular compiler/machine environment.


______________________________________________________

Suggested online readings and information:
Evolving comparators.
Comparators.
Sorts.
______________________________________________________