Número de clasificación 4 con pocas comparaciones

Question

¿Cómo puedo ordenar 4 números en 5 comparaciones?

Answer 1

Toma los números {a, b, c, d}, divididos en 2 conjuntos {a, b} {c, d}. Ordene cada uno de esos 2 conjuntos, de modo que obtenga (e, f) (g, h). Esa es una comparación por conjunto.

Ahora escoja la más baja desde el frente (compare e, g). Eso es ahora tres comparaciones. Elija el siguiente punto más bajo entre (e, h) o (f, g). Eso es cuatro. Compara los dos últimos elementos (es posible que ni siquiera necesites este paso si los dos elementos son del mismo conjunto y, por lo tanto, ya están clasificados). Entonces eso es cinco.

Answer 2

Para ordenar el número ABCD en 5 comparaciones, clasifique AB y CD por separado. Eso requiere 2 comparaciones. Ahora llame merge like in merge sort en las cadenas AB y CD. Eso requiere 3, porque en la primera comparación elegirás A o C. Terminaras teniendo B y CD para fusionar o AB y D. Y aquí solo necesitas 2 comparaciones ya que tanto AB como CD ya están ordenados.

Answer 3

Pseudocódigo:

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 4

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) { //-> 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>