img/home.png

Sort, sorting


And this is a sort program from the first page. A better than Quicksort algorithm, when there are several unique records, so we called it "Several unique" sort. 


$declareint i j k l o p n zero flip 
$dimension field[251]
//Input variable is field[251] - 251 element of array field[] defined by user.
$rinvar field[](0,3)

//Output variable is field[251] - 251 elements of field[] array.
$retvar field[]

$bes
zero=0;     // value 0 stored in a variable
flip=1;     // is still to sort


o=0; p=1; n=250; k=1;
while (k>=i) {
  k=-1;
  while (n>k) {
    k++; l=field[k];
    if (j>l) { field[i]=l; i++; field[k]=j; }
    if (l>j) { i=k; j=field[k]; }
  }
  j=0; n=i-p;
}
$ees
When the above program has only two unique records to proceed, a further optimization with Critticall gives us: 

// The algorithm has been enhanced for 39.7652%
 $DECLAREINT  n o k l critticall1 critticall3 
 $DIMENSION field[251]
 $MINIMIZE LINES 40
 $SOUND ON
 $RINVAR field[](0,1) field[](1,2) field[](4,5)
 $RETVAR field[]

// int field[251]; int n=0;int o=0;int k=0;int l=0;int critticall1=0;int critticall3=0;
$BES
o=250;
n=field[k];
while (o>critticall3) {
    critticall3+=1;
    critticall1=field[critticall3];
    if (critticall1>n) {
        k=critticall3;
        n=critticall1;
    }
    if (n>critticall1) {
        critticall3+=1;
        field[k]=critticall1;
        critticall1=field[critticall3];
        k+=1;
        while (n>critticall1) {
            critticall3+=1;
            field[k]=critticall1;
            critticall1=field[critticall3];
            k+=1;
        }
        critticall3+=1;
        critticall1=field[critticall3];
        if (n>critticall1) {
            field[k]=critticall1;
            k+=1;
        } else {
            while (l>critticall3) {
                critticall3+=1;
                critticall1=field[critticall3];
                if (n>critticall1) {
                    field[k]=critticall1;
                    field[critticall3]=n;
                    k+=1;
                }
            }
            l=o;
        }
    }
}

$EES
Forty percent less instructions are executed this way. It's a conjectural algorithm, but very likely a correct one.
How does it perform against QuickSort, you can see on this animation.

Sorting the sequence
    [1,0,1,0,1,0,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,0,1,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,1,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0]
to
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
        TwoUniqueSort                QuickSort