Отправляет email-рассылки с помощью сервиса Sendsay

Все о Паскале

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "RFpro.ru: Программирование на языке Pascal" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

  Апрель 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
Gescheit

Статистика

1.401 подписчиков
-3 за неделю
←   Все выпуски   →

Все о Паскале


Информационный Канал Subscribe.Ru
Лучшие статьи о паскале!
 Подисчиков:  19
Выпуск номер: 5
Сегодня в выпуске:
1. ) Сортировка Шелла

1. )Сортировка Шелла


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

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

Все о паскале, множество доков, исходники, 15(!) компиляторов и многое другое

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное