|
Страница 9 из 60
Сортировка Шелла
Сортировка Шелла получила свое название по имени ее создате-
ля Д.Л.Шелла. Однако, это название можно считать удачным, так как
выполняемые при сортировке действия напоминают укладывание морс-
ких ракушек друг на друга. ("Ракушка" - одно из значений слова
shell - Примеч. пер.)
Общий метод, который использует сортировку вставкой, приме-
няет принцип уменьшения расстояния между сравниваемыми элемента-
ми. На рис.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. Эта зависи-
мость значительно лучше квадратичной зависимости, которой подчи-
няются рассмотренные ранее алгоритмы сортировки. Однако, прежде
чем вы решите использовать сортировку Шелла, следует иметь в ви-
ду, что быстрая сортировка дает даже еще лучшие результаты. |