Упорядочить 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;

на главную

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[0]<=a[4], a[1]<=a[3]<=a[4]

Случай a[3]>a[4] не возможен, т.к. третье сравнение
и следующие за ним перестановки меняют положение элементов a[3] и a[4]:

  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;

Упорядочить 5 элементов за 7 сравнений

А не могли бы вы сочинить что-нибудь на тему медианной фильтрации? Может быть специальные оптимизированные случаи одномерной и двумерной фильтрации с определённым размером окна (3 и 3x3, 5 и 5х5 и т.д.)?

Упорядочить 5 элементов за 7 сравнений

Обычно медианная фильтрация применяется для обработки изображений. На эту тему существует обширная теория и очень быстрые алгоритмы. Изобрести что-либо новое в этой области чрезвычайно трудно, разве что можно немного улучшить какую-нибудь известную реализацию. Проще найти готовое. ;-)