Шелсорт

Šelsort

Shellsort with gaps 23, 10, 4, 1 in action.
Klasa	Algoritmi sortiranja
Struktura podataka	Niz
Najgora performanca	zavisi od raskoraka
Najbolja performanca	zavisi od raskoraka
Prosečna performanca	zavisi od raskoraka
Najgora prostorna kompleksnost	О(n) ukupan, O(1) pomoćni prostor

Shell sort алгоритам линије у боји

Šelsort (engl. Shellsort) је једноставан алгоритам за сортирање у месту заснован на поређењу елемената. Ово је генерализација сортирања код којих елементи мењају места, као што су Сортирање уметањем или Сортирање мехуром. Елементи који су удаљенији се пореде и замењују места раније него ближи елементи. Започиње се од најудаљенијих елемената. Прву верзију овог алгоритма објавио је Доналд Шел 1959. године. Време извршавања овог алгоритма зависи од секвенца раскорака (енгл. gap) које користи.

Опис

Шелсорт је генерализација алгоритма Сортирање уметањем, која дозвољава замену елемената који нису суседни. Идеја је да се елементи уреде у низ, тако да сваки њен подниз који почиње на било ком индексу, и чини га сваки наредни хти елемент, буде сортиран. Овакав низ је х-сортиран. Почиње се са великим х, што омогућава премештање удаљених елемената у оригиналном низу, и тиме смањује количину премештања која би се јавила ако би само суседни елементи могли да замењују места. Ако је низ к-сортиран, за к мање од х, он је и х-сортиран. Смањујући х у свакој итерацији до вредности 1 гарантује сортитан низ на крају извршавања алгоритма.

Испод је дат пример извршавања Шелсорта, са раскорацима 5, 3 и 1.

${\begin{array}{rcccccccccccc}&a_{1}&a_{2}&a_{3}&a_{4}&a_{5}&a_{6}&a_{7}&a_{8}&a_{9}&a_{10}&a_{11}&a_{12}\\{\hbox{input data:}}&62&83&18&53&07&17&95&86&47&69&25&28\\{\hbox{after 5-sorting:}}&17&28&18&47&07&25&83&86&53&69&62&95\\{\hbox{after 3-sorting:}}&17&07&18&47&28&25&69&62&53&83&86&95\\{\hbox{after 1-sorting:}}&07&17&18&25&28&47&53&62&69&83&86&95\\\end{array}}$

У првом проласку, сортирају се елементи на удаљености 5, односно соритају се поднизови (а₁, а₆, а₁₁), (а₂, а₇, а₁₂), (а₃, а₈), (а₄, а₉), (а₅, а₁₀).

На пример, подниз (а₁, а₆, а₁₁) се од (62, 17, 25) трансофмише у (17, 25, 62). У следећем пролазу врши се 3-сортирање на поднизовима (а₁, а₄, а₇, а₁₀), (а₂, а₅, а₈, а₁₁), (а₃, а₆, а₉, а₁₂). У последњем пролазу 1-сортирање је уобичајено сортирање уметањем над целим низом (а₁,..., а₁₂).

Као што пример илуструје, поднизови који се користе у алгоритму су у почетку кратки. У сваком следећем пролазу они су дузи, али и уређенији услед претходних пролаза. У оба случаја, соритање уметањем ради ефикасно.

Шелсорт није стабилан алгоритам. Елементи са истим вредностима не морају се у резултујућм низу наћи у истом редоследу као у оригиналном. Пошто је заснован на алгоритму уметањем, ради брже што је почетни низ уређенији.

Псеудокод

# Sortirati niz a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (gap in gaps)
{
    # Uraditi sortiranje umetanjem za svaku gap veličinu.
    for (i = gap; i < n; i += 1)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }

}

Гап секвенце

Није лако одредити оптималне вредности за раскораке. Свака секвенца која садржи вредност 1 гарантује коректно сортирање. Међутим, особине алгоритма се доста разликују при различитим вредностима раскорака.

У табели се пореде најчешће предлагане вредности за раскораке. У некима оне зависе од величине улазног низа (Н), док су код других секвенце бесконачне, при чему вредности мање од Н треба посматрати у обрнутом редоследу.

Генерал терм (к ≥ 1)	Цонцрете гапс	Wорст-цасе тиме цомплеxитy	Аутхор анд yеар оф публицатион
$\lfloor N/2^{k}\rfloor$	$\left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1$	$\Theta (N^{2})$ [wхен Н=2п]	Схелл, 1959
$2\lfloor N/2^{k+1}\rfloor +1$	$2\left\lfloor {\frac {N}{4}}\right\rfloor +1,\ldots ,3,1$	$\Theta (N^{3/2})$	Франк & Лазарус, 1960
$2^{k}-1$	$1,3,7,15,31,63,\ldots$	$\Theta (N^{3/2})$	Хиббард, 1963
$2^{k}+1$, префиxед wитх 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}})$	Инцерпи & Седгеwицк, 1985
$4^{k}+3\cdot 2^{k-1}+1$, префиxед wитх 1	$1,8,23,77,281,\ldots$	$O(N^{4/3})$	Седгеwицк, 1986
$9(4^{k-1}-2^{k-1})+1,4^{k+1}-6\cdot 2^{k}+1$	$1,5,19,41,109,\ldots$	$O(N^{4/3})$	Седгеwицк, 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$	?	Гоннет & Baeza-Yates, 1991
$\left\lceil {\frac {9^{k}-4^{k}}{5\cdot 4^{k-1}}}\right\rceil$	$1,4,9,20,46,103,\ldots$	?	Токуда, 1992
ункноwн	$1,4,10,23,57,132,301,701$	?	Циура, 2001

Када бинарна репрезентација броја Н садржи много узастопних нула, Шелсорт, користећи оригиналну Шелову секвенцу, има Θ(Н²) поређења у најгорем случају. На пример, овај случај се јавља када је Н степен двојке, када елементи већи и мањи од медијане заузму немапрне и парне позиције редом, јер се пореде тек у последњој итерацији.

Гоннет и Баеза-Yатес су закључили да Шелсорт у просеку користи најмање поређења када је однос узастопних раскорака близак 2.2. Због тога су се њихова секвенца са односом 2.2 и Токудина секвенца са односом 2.25 показале ефикасним. Међутим, није познато зашто је тако. Седгеwицк предлаже раскораке који имају низак Највећи заједнички делилац или су узајамно прости.

Имајући у виду просечан број поређења, најбоље познате секвенце гапова су 1, 4, 10, 23, 57, 132, 301, 701 и сличне. Ови раскораци су добијени емпиријски. Оптимални раскораци већи од 701 остају непознати, али добри резултати се добијају настављањем ове секвенце по формули $h_{k}=\lfloor 2.25h_{k-1}\rfloor$.

Токудина секвенца, дефинисана формулом $h_{k}=\lceil h'_{k}\rceil$, wхере $h'_{k}=2.25h'_{k-1}+1$, $h'_{1}=1$, се препоручује у пракси.

Сложеност

Важи следећа особина: након х₂-сортирања било ког х₁-сортираног низа, низ остаје х₁-сортиран. Сваки х₁-сортирани и х₂-сортирани низ је такође и (а₁х₁+а₂х₂)-сортиран, за свако ненегативно целобројно а₁ и а₂. Због овога је сложеност Шелсорта у најгорем случају везана за Проблем новчића: за дате узајамно просте бројеве х₁,..., х_н, Фробенијев број г(х₁,..., х_н) је највећи цели број који се не може представити као а₁х₁+ ... +а_нх_н са ненегативним целим бројевима а₁,..., а_н. Користећи познату формулу за овај проблем, можемо одредити сложност Шелсорта у најгорем случају за неке класе секвенци раскорака.

Када су раскораци степени двојке, Еспелид је израчунао да да је просечан број операција $0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}}+O(1)$. Доналд Кнут је одредио просечну сложеност сортирања низа од Н елемената користећи два раскорака (х, 1) која износи $2N^{2}/h+{\sqrt {\pi N^{3}h}}$. Следи да Шелсорт са два проласка, где је х = Θ(Н^1/3), у просеку користи О(Н^5/3) поређења. Ендру Јау је одредио просечну сложеност Шелсорта са три проласка. Његов резултат су прерадили Јансон и Кнут. Просечан број поређења при коришћењу три раскорака (цх, цг, 1), где су х и г узајамно прости, је ${\frac {N^{2}}{4ch}}+O(N)$ у првом, ${\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)$ у другом и $\psi (h,g)N+{\frac {1}{8}}{\sqrt {\frac {\pi }{c}}}(c-1)N^{3/2}+O((c-1)gh^{1/2}N)+O(c^{2}g^{3}h^{2})$ у трећем проласку. ψ(х, г), које се појављује у последњој формули, је функција апроскимативно једнака ${\sqrt {\frac {\pi h}{128}}}g+O(g^{-1/2}h^{1/2})+O(gh^{-1/2})$. Када је х = Θ(Н^7/15) и г = Θ(х^1/5), просечно време сортирања је О(Н^23/15).

На основу експеримената, сматра се да се Шелсорт са Хиббардовим и Кнутовим секвенцама раскорака извршава у О(Н^5/4) времену у просеку, и да Гоннет и Баеза-Yатес-ова секвенца захтевају 0.41НлнН(лн лнН+1/6) премештања елемената у просеку. Апроксимације просечног броја операција раније датих секвенца нису успеле за низове са преко милион елемената.

Следећи граф показује просечан број поређења елемената за различите варијанте Шелсорта. Вредности су подељене теоретском доњом границом лог₂Н!. Секвенца 1, 4, 10, 23, 57, 132, 301, 701 је продужена служећи се формулом $h_{k}=\lfloor 2.25h_{k-1}\rfloor$.

Према Колмогорољевој сложености, доказано је да је доња граница за просечан број операција при м пролазака у Шелсорту: Ω(мН^1+1/м) када је м≤лог₂Н и Ω(мН) wхен м>лог₂Н. Према томе, Шелсорт има могућност да у просеку има О(НлогН) сложеност само када користи секвенце раскорака којима број раскорака расте пропорционално логаритму величине низа. Међутим, није познато да ли Шелсорт може заиста да достигне ову сложеност, која је оптимална за сортирање поређењем.

Према Плаxтону, Поонену и Суелу, сложеност алгоритма у најгорем случају је Ω(Н(логН/лог логН)²).

Примена

Шелсорт се ретко користи у пракси. Врши више операција и користи више кеш меморије процесора од Квиксорта. Међутим, како се може лако имплементирати и како не користи стек простор, неке имплементације qсорт фукције у C библиотеци је користе. На пример, Шелсорт се користи у уЦлибц библиотеци. Из сличних разлога, имплементиран је и у Линукс кренелу.

Литература

• Кнутх, Доналд Е. (1997). „Схелл'с метход”. Тхе Арт оф Цомпутер Программинг. Волуме 3: Сортинг анд Сеарцхинг (2нд изд.). Реадинг, Массацхусеттс: Аддисон-Wеслеy. стр. 83—95. ИСБН 978-0-201-89685-5. 
• Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.

Спољашње везе

• Shellsort