Сортировка Шелла
Сортировка методом Шелла базируется на уже известном нам алгоритме простых вставок.
Смысл ее состоит в раздельной сортировке методом простых вставок нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок:
üдля того, чтобы освободить "правильное" место для очередного элемента, приходится уже сдвигать меньшее количество элементов.
Сортировку Шелла придумал Дональд Л. Шелл.
Ее необычность состоит в том, что она рассматривает весь список как совокупность перемешанных подсписков.
На первом шаге эти подсписки представляют собой просто пары элементов.
На втором шаге в каждой группе по четыре элемента.
При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков, соответственно, падает.
Сортирует элементы массива А[1..n] следующим образом:
Øна первом шаге упорядочиваются элементы n/2 пар (A[i], А[n/2 + i]) для 1 < i < n/2,
Øна втором шаге упорядочиваются элементы в n/4 группах из четырех элементов ( A[i], A[n/4 + i], A[n/2 + i], A[3n/4 + i]) для 1 < i < n/4,
Øна третьем шаге упорядочиваются элементы в n/8 группах из восьми элементов и т.д.;
Øна последнем шаге упорядочиваются элементы сразу во всем массиве А.
На каждом шаге для упорядочивания элементов используется метод сортировки вставками.
Пример реализации сортировки Шелла паскаль:
incr:= n div 2;
while incr>0 do
begin
for i:=incr+1 to n do
begin
j:= i-incr;
while j>0 do
if A[j]>A[j+incr] then
begin
c:= A[j];
A[j]:=A[j+incr];
A[j+incr]:=A[j];
j:=j-incr
end
else j:=0 { останов проверки}
end;
incr:= incr div 2
end;
incr:= n div 2;
while incr>0 do
begin
for i:=incr+1 to n do
begin
j:= i-incr;
while j>0 do
if A[j]>A[j+incr] then
begin
c:= A[j];
A[j]:=A[j+incr];
A[j+incr]:=A[j];
j:=j-incr
end
else j:=0 { останов проверки}
end;
incr:= incr div 2
end;
Полный анализ сортировки Шелла чрезвычайно сложен, и мы не собираемся на нем останавливаться.
Было доказано, что сложность этого алгоритма в наихудшем случае при выбранных нами значениях шага равна O(n3/2).
Полный анализ сортировки Шелла и влияния на сложность последовательности шагов можно найти в третьем томе книги Д. Кнута Искусство программирования, М., Мир.