Естественное (Неймановское) слияние.

Материал из DRKB


Естественное (Неймановское) слияние.

Она объединяются упорядоченные части, спонтанно возникшие в исходном массиве; они могут быть также следствием предыдущей обработки данных. Рассчитывать на одинаковый размер сливаемых частей не приходится.

Записи, идущие в порядке неубывания ключей, сцепляются, образуя подсписок. Минимальный подсписок одна запись.

Пример:

Пусть даны ключи записей

5    7    8    3    9     4    1    7    6

Ищем подсписки

В один общий список соединяются 1-й, 3-й, 5-й и т. д. подсписки, в другой - 2-й, 4-й и т. д. подсписки.

Произведем слияние 1 подсписка 1 списка и 1 подсписка 2 списка, 2 подсписка 1 списка и 2 подсписка 2 списка и т.д.

Будут получены следующие цепи

3 --> 5 --> 7 --> 8 --> 9 и 1 --> 4 --> 7

Подсписок, состоящий из записи "6", пары не имеет и "принудительно" объединяется с последней цепью, принимающей вид 1 --> 4--> 6 --> 7.

При нашем небольшом числе записей 2-й этап, на котором сливаются две цепи, окажется последним.

В общем случае на каждом этапе подсписок - результат слияния начальных подсписков 1 и 2 списка становится началом нового 1-го списка, а результат слияния следующих двух подсписков - началом 2-го списка. Следующие образуемые подсписки поочередно включаются в 1-й и во 2-й список.

Для программной реализации заводят массив sp: элемент sp[i] - это номер записи, которая следует за i-й.

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

repeat { Повторение актов слияний подсписков }
  if A[j].kl < A[i].kl then { Выбирается меньшая запись }
  begin
    sp[k] := j;
    k := j;
    j := sp[j];
    if j <= 0 then { Сцепление с остатком "i"-подсписка }
    begin
      sp[k] := i;
      repeat
        m := i;
        i := sp[i]
      until i <= 0;
    end;
  end
  else
  begin
    sp[k] := i;
    k := i;
    i := sp[i];
    if i <= 0 then { Сцепление с остатком "j"-подсписка }
    begin
      sp[k] := j;
      repeat
        m := j;
        j := sp[j]
      until j <= 0;
    end;
  end;
  if j <= 0 then
  begin
    sp[m] := 0;
    sp[p] := -sp[p];
    i := -i;
    j := -j;
    if j <> 0 then
      p := r;
    k := r;
    r := m;
  end;
until j = 0;


В конец сформированного подсписка всегда заносится нулевая ссылка (sp[m] := 0), ибо он может оказаться последним.

Действие sp[p] := -sp[p] обозначает минусом конец ранее построенного подсписка.

В переменных i,j ссылки на начала новых сливаемых подсписков - со знаком минус; его снимаем. Переход к новым подспискам требует обновления переменных p, k, r


Author: www.structur.h1.ru
Source: http://delphiworld.narod.ru/
ID: 04171