Март 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;
Comments (4)
мне кажется, я нашел ошибку в
мне кажется, я нашел ошибку в рассуждении:
для второй реализации, после трех операций возможны 2 ситуации:
1) a[1] <= a[3] && a[3] <= a[4]
2) a[1] <= a[3] && a[3] > a[4] и вот здесь, мы должны сравнить a[4] с a[1].
После трех сравнений и
После трех сравнений и соответствующих им перестановок,
как и написано в комментарии, мы имеем:
Случай a[3]>a[4] не возможен, т.к. третье сравнение
и следующие за ним перестановки меняют положение элементов a[3] и a[4]:
Упорядочить 5 элементов за 7 сравнений
А не могли бы вы сочинить что-нибудь на тему медианной фильтрации? Может быть специальные оптимизированные случаи одномерной и двумерной фильтрации с определённым размером окна (3 и 3x3, 5 и 5х5 и т.д.)?
Упорядочить 5 элементов за 7 сравнений
Обычно медианная фильтрация применяется для обработки изображений. На эту тему существует обширная теория и очень быстрые алгоритмы. Изобрести что-либо новое в этой области чрезвычайно трудно, разве что можно немного улучшить какую-нибудь известную реализацию. Проще найти готовое. ;-)