Сортировка Шелла
Материал из Википедии — свободной энциклопедии
Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, идея которого состоит в сравнении элементов, стоящих не только рядом, но и на расстоянии друг от друга. Иными словами — сортировка вставками с предварительными «грубыми» проходами.
При сортировке Шелла сначала сравниваются и сортируются между собой ключи, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками. Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки вставками или пузырьком (но она не предпочтительна, так как все равно остается медленной) каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, при сортировке Шелла же это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
- отсутствие потребности в памяти под стек
- отсутствие деградации при неудачных наборах данных — qsort легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла
Часто оказывается, что сортировка Шелла есть самый лучший способ сортировки до, примерно, 1000 элементов.
Содержание |
[править] Пример
Пусть дан список A = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5,3,1.
На первом шаге сортируются подсписки A, составленные из всех элементов A, различающихся на 5 позиций, то есть подсписки A5,1 = (32,66,40), A5,2 = (95,35,43), A5,3 = (16,19,93), A5,4 = (82,75,68), A5,5 = (24,54).
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
[править] Выбор длины промежутков
Среднее время работы алгоритма зависит от длин промежутков (d), на которых будут находиться сортируемые элементы исходного списка на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений (N — длина сортируемого списка):
- при выборе последовательности значений
в худшем случае алгоритм выполнит cN2 операций - все значения (3j − 1) / 2 < N,
; такая последовательность шагов приводит к алгоритму класса O(N3 / 2) - все значения 2i3j < N, где
, в порядке убывания; в таком случае количество операций понижается до O(N(logN)2) - функция, предложенная Робертом Седжвиком inc[i]= 9 * 2i − 9 * 2i / 2 + 1, если i четное и 8 * 2i − 6 * 2(i + 1) / 2 + 1, если i нечетное
При использовании таких приращений среднее количество операций: O(n7 / 6), в худшем случае порядка O(n4 / 3). Обратим внимание на то, что последовательность вычисляется в порядке, противоположном используемому: inc[0] = 1, inc[1] = 5, … Формула дает сначала меньшие числа, затем все большие и большие, в то время как расстояние между сортируемыми элементами, наоборот, должно уменьшаться. Поэтому массив приращений inc вычисляется перед запуском собственно сортировки до максимального расстояния между элементами, которое будет первым шагом в сортировке Шелла. Потом его значения используются в обратном порядке. При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.
[править] Примеры реализаций
[править] Глагол
ЗАДАЧА Шелл(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
КОН
КОН Шелл;
[править] C++
int increment(long inc[], long size) { // inc[] массив, в которые заносятся инкременты // size размерность этого массива int p1, p2, p3, s; p1 = p2 = p3 = 1; s = -1; do {// заполняем массив элементов по формуле Роберта Седжвика if (++s % 2) { inc[s] = 8*p1 - 6*p2 + 1; } else { inc[s] = 9*p1 - 9*p3 + 1; p2 *= 2; p3 *= 2; } p1 *= 2; // заполняем массив, пока текущая инкремента хотя бы в 3 раза меньше количества элементов в массиве } while(3*inc[s] < size); return s > 0 ? --s : 0;// возвращаем количество элементов в массиве } template<class T> void shellSort(T a[], long size) { // inc инкремент, расстояние между элементами сравнения // i и j стандартные переменные цикла // seq[40] массив, в котором хранятся инкременты long inc, i, j, seq[40]; int s;//количество элементов в массиве seq[40] // вычисление последовательности приращений s = increment(seq, size); while (s >= 0) { //извлекаем из массива очередную инкременту inc = seq[s--]; // сортировка вставками с инкрементами inc for (i = inc; i < size; i++) { T temp = a[i]; // сдвигаем элементы до тех пор, пока не дойдем до конца или не упорядочим в нужном порядке for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc) a[j+inc] = a[j]; // после всех сдвигов ставим на место j+inc элемент, который находился на i месте a[j+inc] = temp; } } }
[править] VBA
Sub Sort(Mus() As Long) Dim i As Long, k As Long, Pos As Long Dim l As Long, r As Long, n As Long, tmp As Long l = LBound(Mus) r = UBound(Mus) n = r - l + 1 k = 1 Do k = k * 3 + 1 Loop Until k > n Do k = k \ 3 For i = (k + l) To r Pos = i tmp = Mus(i) Do While Mus(Pos - k) > tmp Mus(Pos) = Mus(Pos - k) Pos = Pos - k If (Pos - k) < l Then Exit Do Loop Mus(Pos) = tmp Next Loop Until k = 1 End Sub
[править] 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; } }
Этот более быстрый
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; } }
[править] 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; } } }
[править] Object Pascal (Delphi)
procedure ShellSort(var Arr : TReal1DArray; N : Integer);
//Arr -массив N -количество элементов в массиве (размер)
var
C : Boolean;
G : Integer;
I : Integer;
J : Integer;
Tmp : Double;
begin
g := n div 2;
repeat
i := g;
repeat
j := i-g;
c := True;
repeat
if Arr[j]<=Arr[j+g] then
begin
c := False;
end
else
begin
Tmp := Arr[j];
Arr[j] := Arr[j+g];
Arr[j+g] := Tmp;
end;
j := j-1;
until not ((j>=0) and C);
i := i+1;
until not (i<=n);
g := g div 2;
until not (g>0);
end;
[править] PHP
function ShellSort($elements,$length) { $k=0; $gap[0]=(int) ($length / 2); while($gap[$k]>1) { $k++; $gap[$k]=(int)($gap[$k-1]/2); }//end while for($i=0;$i<=$k;$i++) { $step=$gap[$i]; for($j=$step;$j<$length;$j++) { $temp=$elements[$j]; $p=$j-$step; while($p>=0 && $temp<$elements[$p]) { $elements[$p+$step]=$elements[$p]; $p=$p-$step; }//end while $elements[$p+$step]=$temp; }//endfor j }//endfor i return $elements; }// end function // Exmaple // $SortedElements=shellsort($UnsortedElements,length of list(an integer)); // e.g: $elements=shellsort($elements,10);
[править] 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
[править] Ruby
n = mass.size - 1 d = n/2 while d >= 1 n.downto(0) do |i| 0.upto(i-d) do |j| if mass[j] > mass[j+d] element = mass[j] mass[j] = mass[j+d] mass[j+d] = element end end end d /= 2 end puts mass
[править] Ссылки
Дональд Эрвин Кнут. Искусство программирования на ЭВМ. Том 3. Сортировка и поиск, 2-е изд. Гл. 5.2.1. ISBN 5-8459-0082-4
