Как я могу сортировать 4 числа в 5 сравнениях?
Сортировка 4 числа с небольшим количеством сравнений
Ответ 1
Принимает числа {a, b, c, d}, разбитые на 2 множества {a, b} {c, d}. Закажите каждый из этих двух наборов, чтобы вы получили (e, f) (g, h). Это одно сравнение за каждый набор.
Теперь выберите нижний из фронта (сравните e, g). Это теперь три сравнения. Выберите следующий минимум из (e, h) или (f, g). Это четыре. Сравните последние два элемента (вам может и не понадобиться этот шаг, если два элемента из одного набора и, следовательно, уже отсортированы). Так что пять.
Ответ 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)
Ответ 3
Чтобы отсортировать номер ABCD в 5 сравнениях, сортируйте AB и CD отдельно. Для этого требуется 2 сравнения. Теперь вызовите merge как в сортировке слияния на строках AB и CD. Для этого требуется 3, потому что при первом сравнении вы либо выберете A, либо C. В итоге вы получите B и CD для слияния или AB и D. И здесь вам просто нужно 2 сравнения, так как оба AB и CD, где уже отсортированы.
Ответ 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) { //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>
Ответ 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]
Ответ 6
Для меньшего количества входов вы можете создать оптимальные сети сортировки, обеспечивающие минимальное количество необходимых сравнений.
Вы можете легко сгенерировать их, используя эту страницу
Сортировка четырех чисел в порядке возрастания:
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;
}
или вы можете реализовать свою собственную процедуру подкачки без дополнительной переменной
(В порядке убывания просто измените знак на <)
Ответ 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, чтобы получить их порядок.