Sort 4 number with few comparisons

How can I sort 4 numbers in 5 compar开发者_运维百科isons?

Takes numbers {a,b,c,d}, split into 2 sets {a,b} {c,d}. Order each of those 2 sets, so you get (e,f) (g,h). That's one comparison per set.

Now pick lowest from the front (compare e,g). That's now three comparisons. Pick next lowest from either (e, h) or (f, g). That's four. Compare the last two elements (you might not even need this step if the two elements are from the same set, and thus already sorted). So that's five.

Pseudocode:

function sortFour(a,b,c,d)
    if a < b
        low1 = a
        high1 = b
    else 
        low1 = b
        high1 = a

    if c < d
        low2 = c
        high2 = d
    else
        low2 = d
        high2 = c

    if low1 < low2
        lowest = low1
        middle1 = low2
    else
        lowest = low2
        middle1 = low1

    if high1 > high2
        highest = high1
        middle2 = high2
    else
        highest = high2
        middle2 = high1

    if middle1 < middle2
        return (lowest,middle1,middle2,highest)
    else
        return (lowest,middle2,middle1,highest)

For smaller number of inputs you can generate optimal sorting networks that provides that minimum number of comparisons necessary.

You can generate them easily using this page

Sorting four numbers in ascending order :

if(num1>num2) swap(&num1,&num2);
if(num3>num4) swap(&num3,&num4);
if(num1>num3) swap(&num1,&num3);
if(num2>num4) swap(&num2,&num4);
if(num2>num3) swap(&num2,&num3);

where

void swap(int *a,int *b)
{
   int temp = *a;
   *a = *b;
   *b = temp; 
}

or you can implement your own swap procedure without extra variable

(For descending order just change the sign to < )

This requires no extra memory or swapping operations just 5 comparisons per sort

def sort4_descending(a,b,c,d):
if a > b:
    if b > c:
        if d > b:
            if d > a:
                return [d, a, b, c]
            else:
                return [a, d, b, c]
        else:
            if d > c:
                return [a, b, d, c]
            else:
                return [a, b, c, d]
    else:
        if a > c:
            if d > c:
                if d > a:
                    return [d, a, c, b]
                else:
                    return [a, d, c, b]
            else:
                if d > b:
                    return [a, c, d, b]
                else:
                    return [a, c, b, d]
        else:
            if d > a:
                if d > c:
                    return [d, c, a, b]
                else:
                    return [c, d, a, b]
            else:
                if d > b:
                    return [c, a, d, b]
                else:
                    return [c, a, b, d]
else:
    if a > c:
        if d > a:
            if d > b:
                return [d, b, a, c]
            else:
                return [b, d, a, c]
        else:
            if d > c:
                return [b, a, d, c]
            else:
                return [b, a, c, d]
    else:
        if b > c:
            if d > c:
                if d > b:
                    return [d, b, c, a]
                else:
                    return [b, d, c, a]
            else:
                if d > a:
                    return [b, c, d, a]
                else:
                    return [b, c, a, d]
        else:
            if d > b:
                if d > c:
                    return [d, c, b, a]
                else:
                    return [c, d, b, a]
            else:
                if d > a:
                    return [c, b, d, a]
                else:
                    return [c, b, a, d]

The aim is to sort 4 elements in 5 comparisons.

Comp 1--> Take any two elements say a,b and compare them its maximum is Max1 and minimum is Min1.

Comp 2--> Take other two elements say c,d and compare them its maximum is Max2 and minimum is Min2.

Comp 3--> Compare Max1 and Max2 to get ultimate Max element.

Comp 4--> Compare Min1 and Min2 to get ultimate Min element.

Comp 5--> Compare the loser of the comparisons in Comp 4 and Comp 5 to get their order.

To sort number ABCD in 5 comparisons, sort AB and CD separately. That requires 2 comparisons. Now call merge like in merge sort on strings AB and CD. That requires 3, because in first comparison you'll either choose A or C. You'll end up having B and CD to merge or AB and D. And here you just need 2 comparisons since both AB and CD where already sorted.

Alg. 3: compare five, this average = 4.28 (#8 average = 5), Similar as #8<br>
compare 01, sort -> 0,1<br>
compare 23, sort -> 2,3<br>
compare 12 -> return or next compare<br>
compare 02, sort -> 0,2<br>
compare 13, sort -> 1,3<br>
compare 12, sort -> 1,2
<code>    
function sort4CH(cmp,start,end,n)
{
var n     = typeof(n)    !=='undefined' ? n     : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var c = [];
c[0] = cmp(arr[n][i+0],arr[n][i+1]);
c[1] = cmp(arr[n][i+2],arr[n][i+3]);
if (c[0]>0) {swap(n,i+0,i+1);}
if (c[1]>0) {swap(n,i+2,i+3);}
c[2] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(c[2]>0)) {return n;}
c[3] = c[0]==0 ? 1 : cmp(arr[n][i+0],arr[n][i+2]);// c[2]
c[4] = c[1]==0 ? 1 : cmp(arr[n][i+1],arr[n][i+3]);// c[2]
if (c[3]>0) {swap(n,i+0,i+2);}
if (c[4]>0) {swap(n,i+1,i+3);}
c[5] = !(c[3]>0 && c[4]>0) ? 1 : (c[0]==0 || c[1]==0 ? -1 : cmp(arr[n]    [i+1],arr[n][i+2]));
if (c[5]>0) {swap(n,i+1,i+2);}
return n;
}
</code>

---------------------

Algoritmus: Insert sort sorted array 1-1, 2-2, 4-4, ... average = 3.96 = 1016/256 (average = 4.62 =1184/256 without previous cmp)
<code>    
// javascript arr[1] = [0,1,2,3]
function sort4DN2(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var c = [];
c[0] = cmp(arr[n][i+0],arr[n][i+1]);
c[1] = cmp(arr[n][i+2],arr[n][i+3]);
if (c[0]>0) {swap(n,i+0,i+1); c[0] = -1;}
if (c[1]>0) {swap(n,i+2,i+3); c[1] = -1;}
c[2] = cmp(arr[n][i+0],arr[n][i+2]);
//1234
if (c[2]>0)
    {
    //2013
    c[3] = c[1]==0 ? c[2] : cmp(arr[n][i+0],arr[n][i+3]);
    if (c[3]>0)
        {
        swap(n,i+0,i+2);
        swap(n,i+1,i+3);
        return n;
    }
    c[4] = c[0]==0 ? c[3] : (c[3]==0 ? 1 : cmp(arr[n][i+1],arr[n][i+3]));
    if (c[4]>0)
        {
        //2013->2031
        tmp = arr[n][i+0];
        arr[n][i+0] = arr[n][i+2];
        arr[n][i+2] = arr[n][i+3];
        arr[n][i+3] = arr[n][i+1];
        arr[n][i+1] = tmp;
        return n;
        }
    // 2013
    tmp = arr[n][i+2];
    arr[n][i+2] = arr[n][i+1];
    arr[n][i+1] = arr[n][i+0];
    arr[n][i+0] = tmp;
    return n;
    }
if (c[2]==0) {
    if (c[0]==0) {
        return n;
        }
    if (c[1]==0) {
        tmp = arr[n][i+1];
        arr[n][i+1] = arr[n][i+2];
        arr[n][i+2] = arr[n][i+3];
        arr[n][i+3] = tmp;
        return n;
        }
    }
c[3] = c[0]==0 ? c[2] : c[2]==0 ? -c[1] : cmp(arr[n][i+1],arr[n][i+2]);
if (c[3]>0)
    {
    c[4] = c[1]==0 ? c[3] : cmp(arr[n][i+1],arr[n][i+3]);
    if (c[4]>0)
        {
        swap(n,i+1,i+2);
        swap(n,i+2,i+3);
        return n;
        }
    swap(n,i+1,i+2);
    return n;
    }
return n;
}
</code>

------------

Algoritmus: Insert sort into middle (av. 4.07 = 1044/256 | 4.53 = 1160/256)
0<br>
1 insert into middle 0 -> [0,1] 01, 10<br>
2 insert into middle 01 -> [1,2] 021, 012 -> [0,2] 021, 201 or [null] 012<br>
3 insert into middle 012 -> [1,3] -> [1,0] or [2,3]...
<code>    
function sort4PA(cmp,start,end,n)
{
//arr[n] = [0,0,3,0];
var n     = typeof(n)    !=='undefined' ? n     : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var tmp = 0;
var i = start;
var c = [];
c[0] = cmp(arr[n][i+0],arr[n][i+1]);
if (c[0]>0) {swap(n,i+0,i+1); c[0] = -1;} //10->01
c[1] = cmp(arr[n][i+1],arr[n][i+2]);
if (c[1]>0) {   //0-1 2
    c[2] = c[0]==0 ? c[1] : cmp(arr[n][i+0],arr[n][i+2]);
    if (c[2]>0) {   //-01 2
        c[3] = cmp(arr[n][i+0],arr[n][i+3]);
        if (c[3]>0) {//2301
            c[4] = cmp(arr[n][i+2],arr[n][i+3]);
            if (c[4]>0) { //0123 -> 3201
                tmp = arr[n][0];
                arr[n][0]=arr[n][3];
                arr[n][3]=arr[n][1];
                arr[n][1]=arr[n][2];
                arr[n][2]=tmp;
                return n;
                }
            swap(n,i+0,i+2);
            swap(n,i+1,i+3);
            return n;
            }
        // 2031
        c[4] = c[0]==0 ? c[3] : cmp(arr[n][i+1],arr[n][i+3]);
        if (c[4]>0) {   //2031
            tmp = arr[n][0];
            arr[n][0]=arr[n][2];
            arr[n][2]=arr[n][3];
            arr[n][3]=arr[n][1];
            arr[n][1]=tmp;
            return n;
            }
        tmp = arr[n][0];
        arr[n][0]=arr[n][2];
        arr[n][2]=arr[n][1];
        arr[n][1]=tmp;
        return n;
        }
    //0-1 2
    c[3] = cmp(arr[n][i+2],arr[n][i+3]);
    if (c[3]>0) {
        c[4] = c[2]==0 ? c[3] : cmp(arr[n][i+0],arr[n][i+3]);
        if (c[4]>0) {//3021
            tmp = arr[n][0];
            arr[n][0]=arr[n][3];
            arr[n][3]=arr[n][1];
            arr[n][1]=tmp;
            return n;
            }
        //0321
        swap(n,i+1,i+3);
        return n;
        }
    // 0-1 23
    c[4] = c[3]==0 ? c[1] : cmp(arr[n][i+1],arr[n][i+3]);
    if (c[4]>0) {   //0231
        tmp = arr[n][1];
        arr[n][1]=arr[n][2];
        arr[n][2]=arr[n][3];
        arr[n][3]=tmp;
        return n;
        }
    //0213
    swap(n,i+1,i+2);
    return n;
    }
c[2] = cmp(arr[n][i+1],arr[n][i+3]);
if (c[2]>0) {
    c[3] = c[0]==0 ? c[2] : cmp(arr[n][i+0],arr[n][i+3]);
    if (c[3]>0) {
        // 3012
        tmp = arr[n][0];
        arr[n][0]=arr[n][3];
        arr[n][3]=arr[n][2];
        arr[n][2]=arr[n][1];
        arr[n][1]=tmp;
        return n;
        }
    // 0312
    tmp = arr[n][1];
    arr[n][1]=arr[n][3];
    arr[n][3]=arr[n][2];
    arr[n][2]=tmp;
    return n;
    }
c[3] = c[1]==0 ? c[2] : c[2]==0 ? -c[1] : cmp(arr[n][i+2],arr[n][i+3]);
if (c[3]>0) {
    swap(n,i+2,i+3);
    }
return n;
}
</code>

Just implemented a branchless function that orders four elements using five comparisons. It can be made into a C++ template to sort any type. Data is not affected, r will contain the indices to access the array in ascending order.

// This function actually returns a char[4], using type punning to bypass C restrictions
int order4(int* values) {
  char r[4], h[2], m[2];
  h[0]=         values[1]<values[0];
  h[1]=2|(char)(values[3]<values[2]);  // 3210 -> {2<3}{0<1}
  r[0]=values[h[1]  ]<values[h[0]  ];
  r[3]=values[h[0]^1]<values[h[1]^1];  // {2<3}{0<1} -> 0<{21}<3
  m[0]=h[r[0]^1];
  m[1]=h[r[3]^1]^1;
  r[2]=values[m[1]]<values[m[0]];      // 0<{21}<3 -> 0<1<2<3
  r[0]=h[r[0]];
  r[1]=m[r[2]];
  r[2]=m[r[2]^1];
  r[3]=h[r[3]]^1;
  _ASSERT(((1<<r[0]) | (1<<r[1]) | (1<<r[2]) | (1<<r[3])) == 15); // Ensure that all elements present
  _ASSERT(values[r[0]]<=values[r[1]] && values[r[1]]<=values[r[2]] && values[r[2]]<=values[r[3]]); // Ensure that elements are sorted
  return *(int*)r;
}