СОРТИРОВКА ПОПАРНЫМ СЛИЯНИЕМ.

Входное множество рассматривается, как последовательность подмножеств, каждое из которых состоит из единственного элемента и, следовательно, является уже упорядоченным. На первом проходе каждые два соседних одноэлементных множества сливаются в одно двухэлементное упорядо-ченное множество. На втором проходе двухэлементные множества сливаютс в 4-элементные упорядоченные множества и т.д. В конце концов получается одно большое упорядоченное множество.

Программный пример 3.18 иллюстрирует сортировку попарным слиянием в ее обменном варианте - выходные множества формируются на месте входных.

 

{===== Программный пример 3.18 =====}

Procedure Sort(var a :Seq);

Var i0,j0,i,j,si,sj,k,ke,t,m : integer;

begin si:=1; { начальный размер одного множества }

while si<N do{цикл пока одно множество не составит весь массив}

begin i0:=1; { нач. индекс 1-го множества пары }

while i0<N do { цикл пока не пересмотрим весь массив }

begin j0:=i0+si; { нач. индекс 2-го множества пары }

i:=i0; j:=j0;

{размер 2-го множества пары может ограничиваться концом массива }

if si>N-j0+1 then sj:=N-j0+1 else sj:=si;

if sj>0 then

begin k:=i0; { нач. индекс слитого множества }

while (i<i0+si+sj) and (j<j0+sj) do

{ цикл пока не исчерпаются оба входные множества }

begin if a[i]>a[j] then

{ если эл-т 1-го <= элемента 2-го, он остается на своем месте, но вых. множество расширяется иначе - освобождается место в вых.множестве и туда заносится эл-т из 2-го множества }

begin t:=a[j];

for m:=j-1 downto k do a[m+1]:=a[m];

a[k]:=t; j:=j+1; {к след. эл-ту во 2-м множестве}

end; { if a[i]>a[j] }

k:=k+1; { вых. множество увеличилось }

i:=i+1; { если был перенос - за счет сдвига, если не было - за счет

перехода эл-та в вых. }

end; { while } end; { if sj>0 }

i0:=i0+si*2; { начало следующей пары }

end; { while i0<N }

si:=si*2; { размер эл-тов пары увеличивается вдвое }

end; { while si<N }

end;

 

Результаты трассировки примера приведены в таблице 3.11. Для каждого прохода показаны множества, которые на этом проходе сливаются. Обратите внимание на обработку последнего множества, оставшегося без пары.

 

Таблица 3.11

 

 

3.9. Прямой доступ и хеширование

В рассмотренных выше методах поиска число проб при поиске в лучшем случае было пропорционально log2(N). Естественно, возникает желание найти такой метод поиска, при котором число проб не зависело бы от размера таблицы, а в идеальном случае поиск сводился бы к одной пробе.