Алгоритъм на Шел

Пример как алгоритъмът на Шел сортира една редица

Алгоритъмът на Шел (на английски: Shellsort) (нар. още метод на Шел, Шел метод) е алгоритъм за сортиране, за който се взема предвид положението на елементите. Той обобщава други сортиращи методи като метода на мехурчето и метода за сортиране чрез вмъкване, като започва сравнението и разменянето на елементите, с онези, които са отдалечени, преди да се извърши сравнението със съседните. Именно тази характеристика на метода го отличава и го прави по-бърз от предшествениците му. Доналд Шел публикува първата реализация на този метод през 1959 г. Времето за изпълнение на алгоритъма на Шел строго зависи от различната последователност, с която работи.

Описание

Алгоритъмът на Шел е обобщение на метода за сортиране чрез вмъкване, като позволява размяна на елементи, които са разделечени. Идеята е да се подреди листът от елементи, като се започне от някъде (обикновено около средата) и се смята, че всеки h-ти елемент дава сортиран лист. Подобен лист се казва, че е h-сортиран. Накрая се получават листове от интервали, всеки от които индивидуално сортиран. Започването с голяма стойност на h, позволява на елементите да се придвижват на големи разстояния и намалява възможността за доста произволни разбърквания. Също така се оставят по-малко на брой операции за малките h-сортирания.

Методът е нестабилен. Той може да смени наредбата на елементи с еднаква стойност. Естественото му поведение е, че работи бързо когато масивът е отчасти сортиран.

Следният пример показва сортиране чрез метода на Шел при разлика съответно 5, 3 и 1:

входни данни:                  80       72      71      30      64      43      98      41       30       01
след 5-сортирне:               43       72      41      30      01      80      98      71       30       64
след 3-сортиране:              01       30      30      64      41      71      43      72       98       80
след 1-сортиране:              01       30      30      41      43      64      71      72       80       98

Имплементация на метода

C

 void shellSortPhase(int arr[], int length, int gap)
 {
     int i;
     for (i = gap; i < length; ++i)
     {
         int value = arr[i];
         int j;
         for (j = i – gap; j >= 0 && arr[j] > value; j -= gap)
         {
             arr[j + gap] = arr[j];
         }
         arr[j + gap] = value;
     }
 }

 void shellSort(int arr[], size_t length)
{
     static const int gaps[] = {1, 4, 10, 23, 57, 132, 301, 701};
     int sizeIndex;

     for (sizeIndex = sizeof(gaps)/sizeof(gaps[0]) – 1; sizeIndex >= 0; --sizeIndex)
         shellSortPhase(arr, length, gaps[sizeIndex]);
 }

Java

public static <T extends Comparable<? super T>>
 void shellSort(T[] arr)
 {
    for (int gap = arr.length / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < arr.length; i++)
        {
            T val = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap].compareTo(val) > 0; j -= gap)
            {
                arr[j] = arr[j - gap];
            }
            arr[j] = val;
        }
    }
}

Гап поредици

Гап (на английски: gap) или т.нар. дупка, представлява разликата между два елемента.

Въпросът при решаването коя гап поредица да се ползва е труден. Всяка една гап поредица, която съдържа една вече получена разлика, представлява вярно сортирана последователност. Независимо от това, получената по този начин реализация, може да бъде доста трудна за метода на Шел.

Таблицата по-долу сравнява най-често срещаните гап поредици. Някои от тях имат намаляващи елементи, които зависят от размера на сортирания масив (N). Други са безкрайно растящи редици, чиито елементи, по-малки от N, би трябвало да бъдат използвани в обратен ред.

Обичаен период (k ≥ 1)	Бетонен гап	Сложност в най- лошия случай	Автор и година на публикацията
$\lfloor N/2^{k}\rfloor$	$\left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1$	$\Theta (N^{2})$ [когато N=2^p]	Шел, 1959
$2^{k}-1$	$1,3,7,15,31,63,\ldots$	$\Theta (N^{3/2})$	Хибърд, 1963
$2^{k}+1$ , префиксно с 1	$1,3,5,9,17,33,65,\ldots$	$\Theta (N^{3/2})$	Папернов & Штасевич, 1965
следващите числа във формулата $2^{p}3^{q}$	$1,2,3,4,6,8,9,12,\ldots$	$\Theta (N\log ^{2}N)$	Прат, 1971
$(3^{k}-1)/2$ , не повече от $\lceil N/3\rceil$	$1,4,13,40,121,\ldots$	$\Theta (N^{3/2})$	Кнут, 1973
$\prod \limits _{\scriptscriptstyle 0\leq q<r \atop \scriptscriptstyle q\neq (r^{2}+r)/2-k}a_{q},{\hbox{where}}$ $r=\left\lfloor {\sqrt {2k+{\sqrt {2k}}}}\right\rfloor ,$ $a_{q}=\min\{n\in \mathbb {N} \colon n\geq (5/2)^{q+1},$ $\forall p\colon 0\leq p<q\Rightarrow \gcd(a_{p},n)=1\}$	$1,3,7,21,48,112,\ldots$	$O(Ne^{\sqrt {8\ln(5/2)\ln N}})$	Инцепри & Седжвик, 1985
$4^{k}+3\cdot 2^{k-1}+1$ , префиксно с 1	$1,8,23,77,281,\ldots$	$O(N^{4/3})$	Седжвик, 1986
$h_{k}=\max \left\{\left\lfloor 5h_{k-1}/11\right\rfloor ,1\right\},h_{0}=N$	$\left\lfloor {\frac {5N}{11}}\right\rfloor ,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N}{11}}\right\rfloor \right\rfloor ,\ldots ,1$	?	Ганет & Баеза-Йейтс, 1991
$\left\lceil {\frac {9^{k}-4^{k}}{5\cdot 4^{k-1}}}\right\rceil$	$1,4,9,20,46,103,\ldots$	?	Токуда, 1992
неизвестен	$1,4,10,23,57,132,301,701$	?	Циура, 2001

Когато двоичното представяне на N съдържа последователни нули, методът използва оригиналната редица на Шел, която прави Θ(N²) сравнения в най-лошия случай.

Най-добрата позната ни гап редица е 1, 4, 10, 23, 57, 132, 301, 701. Оптимални гап редици след 701 остават неизвестни, но добри резултати също могат да бъдат наблюдавани при нарастване на горната редица според следната формула $h_{k}=\lfloor 2.25h_{k-1}\rfloor$ .

Изчислителна сложност

След всяко h₂ сортиране на някой h₁-сортиран масив, масивът остава h₁-сортиран. Всеки h₁-сортиран и h₂-сортиран масив могат също да се представят като (a₁h₁+a₂h₂)-сортирани, за всички неотрицателни целочислени a₁ и a₂. Следователно, сложността в най-лошия случай на метода на Шел е силно свързана с Проблема на Фробениус: за дадени целочислени стойсти h₁,…,h_n с най-малък общ делител 1, Фробениовото число g(h₁,…,h₂) е най-голямото цяло число, което не може да бъде представено като a₁h₁+…+a_nh_n използвайки неотрицателни целочислени a₁,…,a_n. Използвайки познатата формула за Фробениови числа, може да се изчисли сложността в най-лошия случай на метода на Шел. Доказани резултати са показани в по-горната таблица.

Никой от показаните резултати не се интересува от гап поредицата в действителността.

Приложение

Алгоритъмът на Шел не намира широко разпространение в съвременния свят. Причината е, че изпълнява повече операции от бързото сортиране. Независимо от това, фактът, че не използва стека и за имплементацията му е нужно малко парче код, в някои стандартни библиотеки на C, е използван с предимство пред бързото сортиране. Примерно приложение на метода на Шел е в библиотеката uClibc.

Също така методът на Шел може да бъде използван за сортиране на парчета от масиви при интроспективния метод с цел да се предотврати забиване в дълбока рекурсия превишаваща дадената времева граница.