Сортировать 4 числа с несколькими сравнениями

Question

Как мне отсортировать 4 числа в 5 сравнениях?

Answer 1

Принимает числа {a, b, c, d}, разбитые на 2 набора {a, b} {c, d}.Закажите каждый из этих 2 наборов, чтобы вы получили (e, f) (g, h).Это одно сравнение на комплект.

Теперь выберите самое низкое спереди (сравните e, g).Это теперь три сравнения.Выберите следующий самый низкий из (e, h) или (f, g).Это четыре.Сравните последние два элемента (вам может даже не понадобиться этот шаг, если два элемента из одного набора и, таким образом, уже отсортированы).Итак, это пять.

Answer 2

Псевдокод:

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)

Answer 3

Чтобы отсортировать число ABCD в 5 сравнениях, сортируйте AB и CD отдельно.Это требует 2 сравнений.Теперь вызовите merge как в сортировке слиянием для строк AB и CD.Для этого требуется 3, потому что в первом сравнении вы либо выберете A или C. В результате вы получите B и CD для слияния или AB и D. И здесь вам просто нужно 2 сравнения, поскольку и AB, и CD уже отсортированы.1001 *

Answer 4

Для меньшего количества входов вы можете создать оптимальные сети сортировки, обеспечивающие минимальное количество необходимых сравнений.

Вы можете легко сгенерировать их, используя эту страницу

Сортировка четырех чисел в порядке возрастания:

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

, где

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

или вы можете реализовать собственную процедуру подкачки без дополнительной переменной

(в порядке убывания просто измените знак на <) </p>

Answer 5

Это не требует дополнительной памяти или операций подкачки, только 5 сравнений на сортировку

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]

Answer 6

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>

Answer 7

Цель состоит в том, чтобы отсортировать 4 элемента в 5 сравнениях.

Comp 1 -> Возьмите любые два элемента, скажем, a, b и сравните их, его максимум - Max1, а минимум - Min1.

Comp 2 -> Возьмите два других элемента, скажем, c, d и сравните их, его максимум - Max2, а минимум - Min2.

Comp 3 -> Сравните Max1 и Max2, чтобы получить максимальный элемент Max.

Comp 4 -> Сравните Min1 и Min2, чтобы получить конечный элемент Min.

Комп 5 -> Сравните неудачника сравнений в Комп 4 и Комп 5, чтобы получить их порядок.