Библиотечная сортировка
Библиотечная сортировка - это попытка решения проблемы всех сортировок вставками.
Возьмём изначальную простую сортировку вставками. Алгоритм заключается в том, чтобы брать по одному элементы из несортированной части, последовательно искать для каждого из них правильное место в сортированной части и вставлять элемент.
При вставке возникает необходимость раздвинуть сортированную часть, т.е. для вставки одного элемента требуется переместить большое количество других.
Библиотечная сортировка пытается решить эту проблему, используя для сортированной части рабочий массив, который в несколько раз больше исходного. Это позволяет помещать элементы не подряд, а через интервал, оставляя свободные места для последующих вставок.
В этом алгоритме необходимость перемещения большого числа элементов (перебалансировки) возникает не при каждой вставке. Иногда место в которое нужно вставитьь элемент ещё свободно.
Определение места вставки осуществляется бинарным поиском, но поскольку в рабочем массиве много "не занятых" мест, алгоритм нужно модифицировать. Кроме того, для ускорения оказывается разумным отдельно обрабатывать ситуации, когда вставка должна производиться в край сортированной части.
Перебалансировку массива можно делать разными путями. Мы используем глобальную перебалансировку. Весь рабочий массив перетряхивается так, чтобы уже помещённые в него элементы оказались на равных расстояниях между собой и от краёв массива:
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)) |
Метки:
- Войдите или зарегистрируйтесь, чтобы отправлять комментарии