Метод Шелла
Общий метод,
который использует сортировку вставкой,
применяет принцип уменьшения расстояния
между сравниваемыми элементами. На рис.2 показана
схема выполнения сортировки Шелла для мас сива
"оасве". Сначала сортируются все элементы,
которые смещены друг от друга на три позиции.
Затем сортируются все элементы, которые смещены
на две позиции. И, наконец, упорядочиваются все
соседние элементы.
проход 1 f d a c b e
проход 2 c b a f d e
проход 3 a b c e d f
полученный результат a b c d
e f
Рис.2. Сортировка Шелла:
{ сортировка Шелла }
procedure Shell(var item: DataArray;
count:integer);
const
t = 5;
var
i, j, k, s, m: integer;
h: array[1..t] of integer;
x: DataItem;
begin
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
for m := 1 to t do
begin
k:=h[m];
s:=-k;
for i := k+1 to count do
begin
x := item[i];
j := i-k;
if s=0 then
begin
s := -k;
s := s+1;
item[s] := x;
end;
while (x<item[j]) and (j<count) do
begin
item[j+k] := item[j];
j :=
j-k;
end;
item[j+k] :=
x;
end;
end;
end; { конец сортировки Шелла }
При поверхностном взгляде на
алгоритм нельзя сказать, что он дает хороший
результат и даже то, что в результате
получится отсортированный массив. Однако, он
дает и то и другое. Эффективность этого
алгоритма объясняется тем, что при каждом
проходе используется относительно небольшое
число элементов или элементы массива уже
находятся в относительном порядке, а
упорядоченность увеличивается при каждом новом просмотре
данных.
Расстояния
между сравниваемыми элементами могут
изменяться по-разному. Обязательным является
лишь то, что последний шаг должен равняться
единице. Например, хорошие результаты дает
последовательность шагов 9, 5, 3, 2, 1, которая
использована в показанном выше примере. Следует
избегать последовательностей степени двойки,
которые, как показывают сложные математические
выкладки,
снижают эффективность алгоритма сортировки. /Однако,
при исполь зовании таких последовательностей
шагов между сравниваемыми элементами эта
сортировка будет по-прежнему работать правильно/.
Внутренний цикл имеет два условия
проверки. Условие "х<item[j]" необходимо
для упорядочения элементов. Условия "j>0" и
"j<= count" необходимы для того,
чтобы предотвратить выход за
пределы массива "item". Эта дополнительная проверка
в некоторой степени ухудшает сортировку
Шелла. Слегка измененные версии сор тировки
Шелла используют специальные управляющие
элементы, которые не являются в действительности
частью той информации, которая должна
сортироваться. Управляющие элементы имеют граничные
для массива данных значения, т.е. наименьшее и
наибольшее значения. В этом случае не
обязательно выполнять проверку на граничные
значения. Однако, применение таких управляющих
элементов требует специальных знаний о той
информации, которая сортируется, и это сни жает
универсальность процедуры сортировки.
Анализ сортировки Шелла требует решения
некоторых сложных математических задач,
которые выходят за рамки этой книги. Время
выполнения сортировки Шелла пропорционально
n**1.2. Эта зависимость значительно лучше
квадратичной зависимости, которой подчиняются
рассмотренные ранее алгоритмы сортировки. Однако,
прежде чем вы решите использовать сортировку Шелла,
следует иметь в виду, что быстрая сортировка дает
даже еще лучшие результаты.
Метод Шелла
В рассмотренных алгоритмах сортировки запись
перемещается каждый раз только на одну позицию.
При этом среднее время работы будет в лучшем
случае пропорционально n . Методом, существенно
превосходящим простые вставки, при котором
записи перемещаются большими скачками, является
метод Шелла (сорти-
ровка с убывающим шагом). Метод состоит в том, что
упорядочиваемая таблица разделяется на группы
элементов, каждая из которых упорядочивается
методом вставки. В процессе упорядочения размеры
таких
групп увеличиваются до тех пор, пока
все элементы таблицы не войдут в упорядоченную
группу. Выбор очередной упорядочиваемой группы и
ее расположение внутри таблицы производятся так,
чтобы можно было использовать предшествующую
упорядоченность. Группой таблицы называют
последовательность элементов, номера которых
образуют арифметическую прогрессию с разностью h
(h называют шагом группы). В начале процесса
упорядочения выбирается первый шаг группы h1,
который зависит от размера таблицы. Шелл
предложил брать
h1=[n/2], а hi=h((i-1)/2).
В более поздних работах Хиббард показал,
что для ускорения процесса целесообразно
определить шаг h1 по формуле:
h1=2**k+1 , где 2**k < n
<= 2**(k+1).
После выбора h1 методом вставки упорядочиваются
группы, содержащие элементы с номерами позиций
i, i+h1, i+2*h1, ..., i+mi*h1.
При этом i=1,2,...,h1; m[i] - наибольшее целое,
удовлетворяющее неравенству i+m[i]*hi <= n.
Затем выбирается шаг h2<h1 и
упорядочиваются группы, содержащие элементы с номерами позиций
i, i+h2, ..., i+m[i]*h2. Эта процедура со все
уменьшающимися шагами продолжается до тех пор, пока
очередной шаг h[l] станет равным единице (h1>h2>...>hl).
Этот последний этап представляет собой
упорядочение всей таблицы методом вставки. Но так как
исходная таблица упорядочивалась отдельными группами
с последовательным объединением этих групп,
то общее количество сравнений значительно
меньше, чем n /4, требуемое при методе вставки.
Число операций сравнения пропорционально
n*(log2(n))**2 .
Содержание
|
