Сортировка Шелла
Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга.
При сортировке Шелла сначала сравниваются и сортируются между собой ключи, отстоящие один от другого на некотором расстоянии . После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при (то есть, обычной сортировкой вставками. Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки вставками или пузырьком каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, при сортировке Шелла же это число может быть больше).
Пример
Пусть дан список и выполняется его сортировка методом Шелла, а в качестве значений выбраны .
На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, т. е. подсписки , , , , .
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
Выбор длины промежутков
Среднее время работы алгоритма зависит от длин промежутков (), на которых будут находится сортируемые элементы исходного списка на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений ( — длина сортируемого списка):
- при выборе последовательности значений в худшем случае алгоритм выполнит операций
- все значения , ; такая последовательность шагов приводит к алгоритму класса
- все значения , где , в порядке убывания; в таком случае количество операций понижается до
Примеры реализаций
Pascal
uses dos;
type t1=array [1..8000] of integer;
Var i: integer;
A:t1;
n: integer;
h,m,s,ds: word;
Procedure swap (Var i,j: integer);
Var ob: longint;
Begin
ob:=A[i];
A[i]:=A[j];
A[j]:=ob;
end;
procedure Bubble(Var step: integer);
Var i:integer;
f: boolean;
j,b: integer;
Begin
for j:=1 to step do
repeat
f:=true;
i:=j;
while i+step <= n do
begin
if A[i]> A[i+ step] then
begin
b:=i+step;
swap(i,b);
f:=false
end;
inc (i,step);
end;
until(f);
end;
procedure shelsort (Var steps:t1; Var n: integer);
Var i,k: byte;
Begin
k:=1;
steps[1]:=1;
while steps[k]<=n do
begin
inc(k);
steps[k]:=steps[k-1]*3+1;
end;
for i:=k downto 1 do
bubble (steps[i]);
end;
BEGIN
randomize;
writeln ('vvedite kol-vo chisel');
readln(n);
writeln (' nash massiv');
for i:=1 to n do
A[i]:=random(3000);
settime (0,0,0,0);
shelsort (A,n);
gettime (h,m,s,ds);
for i:=1 to n do
write(' ',A[i],' ');
write (' chasi ',h,' ','minuti ',m,' ',' secundi ',s,' ','dolisecundi ',' ',ds)
END.
Глагол
ЗАДАЧА Шелл(a+: РЯД ИЗ ЦЕЛ);
ПЕР
b,i,j,k,h: ЦЕЛ;
УКАЗ
b:=РАЗМЕР(a)-1;
k:=b ДЕЛИТЬ 2;
ПОКА k>0 ВЫП
ОТ i:=1 ДО b-k ВЫП
j:=i;
ПОКА (j>=1) И (a[j]>a[j+k]) ВЫП
h:=a[j];
a[j]:=a[j+k];
a[j+k]:=h;
УМЕНЬШИТЬ(j);
КОН;
КОН;
k:=k ДЕЛИТЬ 2
КОН
КОН Шелл;
Java
void sort_shell(int[] a)
{ int i, j, k, h, m=0, b=a.length;
int[] d = { 1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711, 11969, 27901,
84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
58548857, 157840433, 410151271, 1131376761, 2147483647 };
while (d[m] < b)
++m;
while (--m >= 0)
{ k = d[m];
for (i=k; i<b; i++) // k-сортировка
{ j=i;
h=a[i];
while ((j >= k) && (a[j-k] > h))
{ a[j]=a[j-k];
j = j-k;
}
a[j] = h;
}
}
}
Python
def shellsort(a):
def new_increment(a):
i = int(len(a) / 2)
yield i
while i != 1:
if i == 2:
i = 1
else:
i = int(numpy.round(i/2.2))
yield i
for increment in new_increment(a):
for i in xrange(increment, len(a)):
for j in xrange(i, increment-1, -increment):
if a[j - increment] < a[j]:
break
a[j],a[j - increment] = a[j - increment],a[j]
return a
PHP
function sort_shell($a)
{
$n = count($a);
$step = $n / 2;
while ($step > 0)
{
for ($i=0; $i<($n-$step); $i++)
{
$j = $i;
while ( ($j >= 0) && ($a[$j] > $a[$j+$step]) )
{
$tmp = $a[$j];
$a[$j] = $a[$j+$step];
$a[$j+$step] = $tmp;
$j--;
}
}
$step /= 2;
}
return $a;
}
C++
template <class T>
void Shell_sort( T a[], const int n )
{
for(int step = n/2 ; step>0 ; step >>= 1){
for( int i=0; i<(n-step); ++i ){
int j = i;
while ( (j>=0) && (a[j]>a[j+step]) ){
T tmp = a[j];
a[j] = a[j+step];
a[j+step] = tmp;
--j;
}
}
}
}
C#
void shellSort(int[] arr)
{
int j;
int step = arr.Length / 2;
while (step > 0)
{
for (int i = 0; i < (arr.Length - step); i++)
{
j = i;
while ((j >= 0) && (arr[j] > arr[j + step]))
{
int tmp = arr[j];
arr[j] = arr[j + step];
arr[j + step] = tmp;
j--;
}
}
step = step / 2;
}
}
this is more quickly
private void shellSort(int[] vector)
{
int step = vector.Length / 2;
while (step > 0)
{
int i, j;
for (i = step; i < vector.Length; i++)
{
int value = vector[i];
for (j = i - step; (j >= 0) && (vector[j] > value); j -= step)
vector[j + step] = vector[j];
vector[j + step] = value;
}
step /= 2;
}
}
Ruby
def shllsrt(a)
d=(a.size-1)/2
while d>0
for i in 1..a.size-d
while i>=1 && a[i]>a[i+d]
a[i],a[i+d],i=a[i+d],a[i],i-d
end
end
d/=2
end
a
end
Ссылки
Дональд Эрвин Кнут. Искусство программирования на ЭВМ. Том 3. Сортировка и поиск, 2-е изд. Гл. 5.2.1. ISBN 5-8459-0082-4