СОРТИРОВКА ПОПАРНЫМ СЛИЯНИЕМ.
Входное множество рассматривается, как последовательность подмножеств, каждое из которых состоит из единственного элемента и, следовательно, является уже упорядоченным. На первом проходе каждые два соседних одноэлементных множества сливаются в одно двухэлементное упорядо-ченное множество. На втором проходе двухэлементные множества сливаютс в 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). Естественно, возникает желание найти такой метод поиска, при котором число проб не зависело бы от размера таблицы, а в идеальном случае поиск сводился бы к одной пробе.