TURBO PASCAL

Новости

Сортировка Шелла

Сортировка Шелла получила свое название по имени ее создате- ля Д.Л.Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морс- ких ракушек друг на друга. ("Ракушка" - одно из значений слова 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 () do begin
item[j+k] := item[j];
j := j-k;
end;
item[j+k] := x;
end;
end;
end; { конец сортировки Шелла }

При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится от- сортированный массив. Однако, он дает и то и другое. Эффектив- ность этого алгоритма объясняется тем, что при каждом проходе ис- пользуется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.

Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг дол- жен равняться единице. Например, хорошие результаты дает последо- вательность шагов 9, 5, 3, 2, 1, которая использована в показан- ном выше примере. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. /Однако, при исполь- зовании таких последовательностей шагов между сравниваемыми эле- ментами эта сортировка будет по-прежнему работать правильно

Внутренний цикл имеет два условия проверки. Условие "х0" и "j<=count" необходимы для того, чтобы предотвратить выход за пределы массива "item". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сор- тировки Шелла используют специальные управляющие элементы, кото- рые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значе- ния. Однако, применение таких управляющих элементов требует спе- циальных знаний о той информации, которая сортируется, и это сни- жает универсальность процедуры сортировки.

Анализ сортировки Шелла требует решения некоторых сложных математических задач, которые выходят за рамки этой книги. Время выполнения сортировки Шелла пропорционально n**1.2. Эта зависи- мость значительно лучше квадратичной зависимости, которой подчи- няются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в ви- ду, что быстрая сортировка дает даже еще лучшие результаты.

По всем интересующим вопросампрошу писать на электронный адрес

Сортировка Шелла

(с)Все права защищены