排序4号码和几个比较

Question

如何在5次比较中排序4个号码？

Answer 1

将数字{a，b，c，d}分成2组{a，b} {c，d}。 为这2套中的每一套排序，所以你得到（e，f）（g，h）。这是每组一个比较。

现在从前面选择最低（比较e，g）。现在是三个比较。 从（e，h）或（f，g）中选取下一个最低的。那是四。 比较最后两个元素（如果两个元素来自同一个集合，并且已经排序，则可能甚至不需要此步骤）。那是五点。

Answer 2

要对5个比较中的ABCD进行排序，请分别对AB和CD进行排序。这需要2个比较。现在调用像字符串AB和CD上合并排序的合并。这需要3，因为在第一次比较中，您将选择A或C.您最终将拥有B和CD来合并，或AB和D.在这里您只需要进行2次比较，因为AB和CD都已经排序。

Answer 3

伪代码：

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>