Упорядочить 5 элементов за 7 сравнений
Март 13, 2011 —
Шарахов А.П.
Сортировка 5 элементов при помощи минимального числа сравнений - довольно известная старая задача.
Нетрудно найти решение, но довольно трудно придать алгоритму сколько-нибудь элегантную форму.
Сначала мы, как обычно, при помощи трех сравнений отыскиваем минимальный элемент в двух парах. При этом после третьего сравнения переставим 4, а не 2 элемента. Далее остается единообразно выполнить вставку остальных двух элементов в сбалансированное дерево из трех элементов. На каждую вставку нам потребуется по 2 сравнения. Всего - 7 сравнений:
type
T5Items= array of integer;
//Sort 5 items using 7 comparisons
procedure Sort5Items(a: T5Items);
var
t: integer;
begin;
if a[4]<a[0] then begin;
t:=a[4]; a[4]:=a[0]; a[0]:=t;
end;
if a[3]<a[1] then begin;
t:=a[3]; a[3]:=a[1]; a[1]:=t;
end;
if a[1]<a[0] then begin;
t:=a[1]; a[1]:=a[0]; a[0]:=t;
t:=a[4]; a[4]:=a[3]; a[3]:=t;
end;
//now: a[0]<=a[4], a[0]<=a[1]<=a[3]
//insert a[2] into a[0]<=a[1]<=a[3]
if a[2]<a[1] then begin;
t:=a[2]; a[2]:=a[1];
if t<a[0] then begin; a[1]:=a[0]; a[0]:=t; end
else a[1]:=t;
end
else if a[3]<a[2] then begin;
t:=a[2]; a[2]:=a[3]; a[3]:=t;
end;
//now: a[0]<=a[4], a[0]<=a[1]<=a[2]<=a[3]
//insert a[4] into a[0]<=a[1]<=a[2]<=a[3]
if a[4]<a[2] then begin;
t:=a[4]; a[4]:=a[3]; a[3]:=a[2];
if t<a[1] then begin; a[2]:=a[1]; a[1]:=t; end
else a[2]:=t;
end
else if a[4]<a[3] then begin;
t:=a[4]; a[4]:=a[3]; a[3]:=t;
end;
end;Симметричный вариант с поиском максимального элемента из двух пар:
//Sort 5 items using 7 comparisons
procedure OtherSort5Items(a: T5Items);
var
t: integer;
begin;
if a[4]<a[0] then begin;
t:=a[4]; a[4]:=a[0]; a[0]:=t;
end;
if a[3]<a[1] then begin;
t:=a[3]; a[3]:=a[1]; a[1]:=t;
end;
if a[4]<a[3] then begin;
t:=a[4]; a[4]:=a[3]; a[3]:=t;
t:=a[1]; a[1]:=a[0]; a[0]:=t;
end;
//now: a[0]<=a[4], a[1]<=a[3]<=a[4]
//insert a[2] into a[1]<=a[3]<=a[4]
if a[3]<a[2] then begin;
t:=a[2]; a[2]:=a[3];
if a[4]<t then begin; a[3]:=a[4]; a[4]:=t; end
else a[3]:=t;
end
else if a[2]<a[1] then begin;
t:=a[2]; a[2]:=a[1]; a[1]:=t;
end;
//now: a[0]<=a[4], a[1]<=a[2]<=a[3]<=a[4]
//insert a[0] into a[1]<=a[2]<=a[3]<=a[4]
if a[2]<a[0] then begin;
t:=a[0]; a[0]:=a[1]; a[1]:=a[2];
if a[3]<t then begin; a[2]:=a[3]; a[3]:=t; end
else a[2]:=t;
end
else if a[1]<a[0] then begin;
t:=a[0]; a[0]:=a[1]; a[1]:=t;
end;
end;Проверить решение можно при помощи следующего кода:
//Testing
procedure TForm1.Button1Click(Sender: TObject);
var
a: T5Items;
i, j, no, count, map, tmp, bit: integer;
s: string;
begin;
Memo1.Lines.Clear;
SetLength(a,5);
for i:=0 to 5*4*3*2*1 - 1 do begin;
no:=i;
map:=-1;
for j:=0 to 4 do begin;
count:=no mod (5-j);
no:=no div (5-j);
tmp:=map;
repeat;
bit:=tmp;
tmp:=tmp and (tmp-1);
dec(count);
until count<0;
bit:=bit xor tmp;
map:=map xor bit;
a[j]:=bit;
end;
s:=Format('%d %d %d %d %d',[a[0],a[1],a[2],a[3],a[4]]);
Sort5Items(a);
s:=s + ' --> ' + Format('%d %d %d %d %d %d',[a[0],a[1],a[2],a[3],a[4], i]);
Memo1.Lines.Add(s);
end;
end;