Добавить комментарий

Delphi

Библиотечная сортировка

Библиотечная сортировка - это попытка решения проблемы всех сортировок вставками.

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

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

Библиотечная сортировка пытается решить эту проблему, используя для сортированной части рабочий массив, который в несколько раз больше исходного. Это позволяет помещать элементы не подряд, а через интервал, оставляя свободные места для последующих вставок. 

В этом алгоритме необходимость перемещения большого числа элементов (перебалансировки) возникает не при каждой вставке. Иногда место в которое нужно вставитьь элемент ещё свободно.

Определение места вставки осуществляется бинарным поиском, но поскольку в рабочем массиве много "не занятых" мест, алгоритм нужно модифицировать. Кроме того, для ускорения оказывается разумным отдельно обрабатывать ситуации, когда вставка должна производиться в край сортированной части.

Перебалансировку массива можно делать разными путями. Мы используем глобальную перебалансировку. Весь рабочий массив перетряхивается так, чтобы уже помещённые в него элементы оказались на равных расстояниях между собой и от краёв массива:

type
  TAI = array of integer;
...
    const
          iNull = -2147483648; // значение "незаполненной" ячейки

    procedure GlobalRebalance(var W: TAI);
    const page = 10; // Шаг увеличения размера rb
    var
        rb      : TAI;     // Рабочий массив для хранения заполненных ячеек.
        current : integer;
        step    : integer;
        i       : integer;
    begin
      Setlength(rb, page);
      // Выделим все заполенные ячейки из W во
      //  внутренний массив rb c сохранением порядка.
      current := -1;
      for i := Low(W) to High(W) do
      begin
        if W[i]<>iNull then
        begin
          inc(current);
          // при необходимости увеличим rb
          if current>High(rb) then
            setLength(rb, Length(rb)+page);

          rb[current] := W[i];
          W[i]        := iNull; // Из W значения убираем.
        end;
      end;
      // Теперь W пуст, все значения перенесены в rb с сохранением порядка
      //  и rb[current] - последний из этих элементов.
      // Рассчитаем шаг, с которым нужно разместить элементы,
      //  чтобы они расположились в W равномерно с одинаковыми промежутками.
      step := trunc((Length(W)+1) / (current+2));
      // Возвращаем значения в W.
      for i := 0 to current do
        W[(i+1)*step-1] := rb[i];
    end;

Отдельный вопрос, во сколько раз рабочий массив должен быть больше исходного. Чем меньше разница, тем чаще нужно будет делать перебалансировку. Чем больше, тем дольше будут проходить поиски соседнего элемента. 

Для нашего варианта перебалансировки коэффициент увеличения не может быть меньше 2. Иначе, после глобальной перебалансировки некоторые элементы могут остаться рядом, и если это именно те элементы, между которыми нам нужно получить промежуток, - это приведёт к краху алгоритма.

Сама сортировка может быть реализована так:

type
  TAI = array of integer;
...
procedure LibrarySort(var A: TAI);
const
      e = 2; // во сколько раз рабочий массив больше исходного
      iNull = -2147483648; // значение "незаполненной" ячейки
var
    W : TAI;     // Рабочий массив
    i : Integer;

    Left, Right,
    Center : integer;

    l,r: integer;

    // Найти первую непустую позицию.
    // Поиск с позициии iStart.
    // Поиск идёт СЛЕВА НАПРАВО.
    Function FindLeft(iStart: integer):integer;
    begin
      result := iStart;
      while W[result] = iNull do
        inc(result);
    end;

    // Найти первую непустую позицию.
    // Поиск с позициии iStart.
    // Поиск идёт СПРАВА НАЛЕВО.
    Function FindRight(iStart: integer):integer;
    begin
      result := iStart;
      while W[result] = iNull do
        dec(result);
    end;

    // Полная перебалансировка массива W.
    procedure GlobalRebalance(var W: TAI);
    ...
    begin
      ...
    end;

    // Попытка добавления элемента с левого края.
    function LeftInsert(iValue: integer): boolean;
    var
        i: integer;
    begin
      // Ищем самый левый заполненный элемент.
      i := FindLeft(Low(W));

      // Если iValue должно находиться левее...
      if (i>High(W)) or (iValue<=W[i]) then
      begin
        // Если места слева нет, - перебалансировка.
        if i=Low(W) then GlobalRebalance(W);

        // ...вставляем значение.
        W[(Low(W)+i) div 2] := iValue;
        result := true;
      end
        else result := false;
    end;

    // Попытка добавления элемента с правого края.
    function RightInsert(iValue: integer): boolean;
    var
        i: integer;
    begin
      // Ищем самый правый заполненный элемент.
      i := FindRight(High(W));

      // Если iValue должно находиться ещё правее...
      if (i<Low(W)) or (iValue>=W[i]) then
      begin
        // Если места справа нет, - перебалансировка.
        if i=High(W) then GlobalRebalance(W);

        // ...вставляем значение.
        W[(High(W)+i) div 2 +1] := iValue;
        result := true;
      end
        else result := false;
    end;


begin
  // Создаём рабочий массив.
  SetLength(W, e*(Length(A)+1) -1);
  for i := Low(W) to High(W) do
    W[i] := iNull;

  i := Low(A);
  // A - исходный массив, анализируем его элементы по одному,
  //  находя для них место в W.
  // Первый элемент просто поставим в середину.
  W[(High(W)+Low(W)) div 2] := A[i];
  inc(i);
  // A[i] - текущий анализируемый элемент.
  while i <= High(A) do
  begin
    // Если не вставилось по краям,
    if not(LeftInsert(A[i])) and
       not(RightInsert(A[i])) then
    begin // начинаем бинарный поиск места вставки.
      // Находим начальные границы диапазона.
      Left  := FindLeft (Low(W));
      Right := FindRight(High(W));
      // Место, в которое нужно вставить, где-то между Left и Right
      // Пока диапазон не сошёлся...
      while Right-left>1 do
      begin
        // Текущее серединное значение.
        Center := (Left+Right) div 2;
        // Если ячейка W[Center] не заполнена,
        //  найдём первую заполненную слева от Center.
        l := FindRight(Center);
        if W[l]<A[i] then // Если найденное значение всё ещё меньше A[i],
        begin
          Left := l; // подтянем левую границу.
          r := FindLeft(Center); // и займёмся правой стороной.
          if W[r]>A[i] // Если найденное справа значение больше A[i],
            then Right := r // подтянем правую границу.
            else if W[r]<A[i] // Если найденное справа значение меньше A[i],
                   then Left := r // продолжим сдвигать левую границу.
                   else begin //  Если найденное справа значение равно A[i],
                          // Попытаемся положить значение из A[i] рядом с
                          // W[r] без пропусков.
                          if W[r-1] = iNull then // Если это возможно,
                          begin // диапазон сошёлся, настроим его.
                            Right :=r;
                            Left  :=r-2;
                          end
                            else // Если места нет, схлопнем диапазон,
                              Right := Left; // это вызовет перебалансировку.
                          break;
                        end;
        end
          else
        begin
          if W[l]>A[i] // Если найденное слева значение больше A[i],
            then Right := l // передвинем туда правую границу диапазона.
            else begin // Если найденное слева значение равно A[i],
                   // Попытаемся положить значение из A[i] рядом с
                   // W[l] без пропусков.
                   if W[l+1]=iNull then // Если место есть,
                   begin // диапазон сошёлся, настроим его.
                     Left  := l;
                     Right := l+2;
                   end
                     else // Если места нет, схлопнем диапазон,
                       Right := Left; // это вызовет перебалансировку.
                   break;
                 end;
        end;
        // Если границы диапазона перестали двигаться - выходим из цикла.
        if (l=Left) and (r=Right) then break;
      end;
      // Теперь мы знаем, что наше A[i] нужно вставить между W[Left] и W[Right].
      // Если там есть место для одно элемента,
      if Right-Left>1 then
      begin // Поместим A[i] в середину обнаруженного интервала.
        W[(Right+Left) div 2] := A[i];
        inc(i);
      end
        else // Если места нет,
          GlobalRebalance(W); // перебалансировка.
    end
      else inc(i);
  end;

  // Вернём значения в массив A.
  l := Pred(Low(W));
  for i := Low(A) to High(A) do
  begin
    l := FindLeft(l+1);
    A[i] := W[l];
  end;
end;

 

Сложность:

Максимальная O(N2)
Минимальная O(N)
Средняя O(N(logN))

 

Filtered HTML

  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Допустимые HTML-теги: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Строки и абзацы переносятся автоматически.
  • Вы можете цитировать другие сообщения, используя тэг [quote]

Plain text

  • HTML-теги не обрабатываются и показываются как обычный текст
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и абзацы переносятся автоматически.