Изворни код странице Šelsort

{{Infobox Algorithm-lat
 |class=[[Algoritmi sortiranja]]
 |image=[[Датотека:Sorting shellsort anim.gif|Step-by-step visualisation of Shellsort]]<br /><small>Shellsort with gaps 23, 10, 4, 1 in action.</small>
 |data=[[Niz]]
 |time=zavisi od raskoraka
 |best-time=zavisi od raskoraka
 |average-time=zavisi od raskoraka
 |space=О(n) ukupan, O(1) pomoćni prostor
 |optimal=Ne
}}
[[Датотека:Shell sorting algorithm color bars.svg|мини|Shell sort алгоритам линије у боји]]
'''Šelsort''' ({{jez-en|Shellsort|el}}) je jednostavan [[algoritam za sortiranje u mestu]] zasnovan na poređenju elemenata. Ovo je generalizacija sortiranja kod kojih elementi menjaju mesta, kao što su [[Sortiranje umetanjem]] ili [[Sortiranje mehurom]]. Elementi koji su udaljeniji se porede i zamenjuju mesta ranije nego bliži elementi. Započinje se od najudaljenijih elemenata. Prvu verziju ovog algoritma objavio je [[Donald Šel]] 1959. godine.<ref name="Shell">{{Cite journal
 |url          = http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
 |last         = Shell
 |first        = D.L.
 |title        = A High-Speed Sorting Procedure
 |journal      = Communications of the ACM
 |volume       = 2
 |issue        = 7
 |year         = 1959
 |doi          = 10.1145/368370.368387
 |pages        = 30–32
 |access-date  = 08. 01. 2014
 |archive-date = 30. 08. 2017
 |archive-url  = https://web.archive.org/web/20170830020037/http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf
 |url-status   = dead
}}</ref><ref>-{Some older textbooks and references call this the "Shell-Metzner" sort after Marlene Metzner Norton, but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it." See}- {{Cite web|title=Shell sort | publisher =National Institute of Standards and Technology
|url=http://www.nist.gov/dads/HTML/shellsort.html
|accessdate = 17. 7. 2007. }}</ref> Vreme izvršavanja ovog algoritma zavisi od sekvenca raskoraka ({{jez-eng-lat|gap}}) koje koristi.
== Opis ==
Šelsort je generalizacija algoritma [[Sortiranje umetanjem]], koja dozvoljava zamenu elemenata koji nisu susedni. Ideja je da se elementi urede u niz, tako da svaki njen podniz koji počinje na bilo kom indeksu, i čini ga svaki naredni ''h''ti element, bude sortiran. Ovakav niz je ''h''-sortiran. Počinje se sa velikim ''h'', što omogućava premeštanje udaljenih elemenata u originalnom nizu, i time smanjuje količinu premeštanja koja bi se javila ako bi samo susedni elementi mogli da zamenjuju mesta. Ako je niz ''k''-sortiran, za ''k'' manje od ''h'', on je i ''h''-sortiran. Smanjujući ''h'' u svakoj iteraciji do vrednosti 1 garantuje sortitan niz na kraju izvršavanja algoritma.

Ispod je dat primer izvršavanja Šelsorta, sa raskoracima 5, 3 i 1.

<math>
\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}
</math>

U prvom prolasku, sortiraju se elementi na udaljenosti 5, odnosno soritaju se podnizovi (''a''<sub>1</sub>, ''a''<sub>6</sub>, ''a''<sub>11</sub>), (''a''<sub>2</sub>, ''a''<sub>7</sub>, ''a''<sub>12</sub>), (''a''<sub>3</sub>, ''a''<sub>8</sub>), (''a''<sub>4</sub>, ''a''<sub>9</sub>), (''a''<sub>5</sub>, ''a''<sub>10</sub>).

Na primer, podniz (''a''<sub>1</sub>, ''a''<sub>6</sub>, ''a''<sub>11</sub>) se od (62, 17, 25) transofmiše u (17, 25, 62). U sledećem prolazu vrši se 3-sortiranje na podnizovima (''a''<sub>1</sub>, ''a''<sub>4</sub>, ''a''<sub>7</sub>, ''a''<sub>10</sub>), (''a''<sub>2</sub>, ''a''<sub>5</sub>, ''a''<sub>8</sub>, ''a''<sub>11</sub>), (''a''<sub>3</sub>, ''a''<sub>6</sub>, ''a''<sub>9</sub>, ''a''<sub>12</sub>). U poslednjem prolazu 1-sortiranje je uobičajeno sortiranje umetanjem nad celim nizom (''a''<sub>1</sub>,..., ''a''<sub>12</sub>).

Kao što primer ilustruje, podnizovi koji se koriste u algoritmu su u početku kratki. U svakom sledećem prolazu oni su duzi, ali i uređeniji usled prethodnih prolaza. U oba slučaja, soritanje umetanjem radi efikasno.

Šelsort nije stabilan algoritam. Elementi sa istim vrednostima ne moraju se u rezultujućm nizu naći u istom redosledu kao u originalnom. Pošto je zasnovan na algoritmu umetanjem, radi brže što je početni niz uređeniji.

== Pseudokod ==


 ''# 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
     }
 
 }

== Gap sekvence ==

Nije lako odrediti optimalne vrednosti za raskorake. Svaka sekvenca koja sadrži vrednost 1 garantuje korektno sortiranje. Međutim, osobine algoritma se dosta razlikuju pri različitim vrednostima raskoraka.

U tabeli se porede najčešće predlagane vrednosti za raskorake. U nekima one zavise od veličine ulaznog niza (''N''), dok su kod drugih sekvence beskonačne, pri čemu vrednosti manje od ''N'' treba posmatrati u obrnutom redosledu.

:{| class="wikitable"
|- style="background-color: #efefef;"
! General term (''k'' ≥ 1)
! Concrete gaps
! Worst-case<br />time complexity
! Author and year of publication
|----
| <math>\lfloor N / 2^k \rfloor</math>
| <math>\left\lfloor\frac{N}{2}\right\rfloor,
        \left\lfloor\frac{N}{4}\right\rfloor, \ldots, 1</math>
| <math>\Theta(N^2)</math> [when ''N''=2<sup>''p''</sup>]
| [[Donald Shell|Shell]], 1959
|----
| <math>2 \lfloor N / 2^{k+1} \rfloor + 1</math>
| <math>2 \left\lfloor\frac{N}{4}\right\rfloor + 1, \ldots, 3, 1</math>
| <math>\Theta(N^{3/2})</math>
| Frank & Lazarus, 1960
|----
| <math>2^k - 1</math>
| <math>1, 3, 7, 15, 31, 63, \ldots</math>
| <math>\Theta(N^{3/2})</math>
| Hibbard, 1963
|----
| <math>2^k + 1</math>, prefixed with 1
| <math>1, 3, 5, 9, 17, 33, 65, \ldots</math>
| <math>\Theta(N^{3/2})</math>
| Papernov & Stasevich, 1965
|----
| successive numbers of the form <math>2^p 3^q</math>
| <math>1, 2, 3, 4, 6, 8, 9, 12, \ldots</math>
| <math>\Theta(N \log^2 N)</math>
| [[Vaughan Ronald Pratt|Pratt]], 1971
|----
| <math>(3^k - 1) / 2</math>, not greater than <math>\lceil N / 3 \rceil</math>
| <math>1, 4, 13, 40, 121, \ldots </math>
| <math>\Theta(N^{3/2})</math>
| [[Donald Knuth|Knuth]], 1973
|----
| <math>\prod
  \limits_{\scriptscriptstyle 0\le q<r\atop
           \scriptscriptstyle q\neq(r^2+r)/2-k}a_q, \hbox{where}</math>
:<math>r = \left\lfloor \sqrt{2k+\sqrt{2k}} \right\rfloor,</math>
:<math>a_q=\min\{n\in\mathbb{N}\colon n\ge(5/2)^{q+1},</math>
:<math>\forall p\colon0\le p<q\Rightarrow\gcd(a_p,n)=1\}</math>
| <math>1, 3, 7, 21, 48, 112, \ldots</math>
| <math>O(N e^\sqrt{8\ln(5/2)\ln N})</math>
| Incerpi & [[Robert Sedgewick (computer scientist)|Sedgewick]], 1985
|----
| <math>4^k + 3\cdot2^{k-1} + 1</math>, prefixed with 1
| <math>1, 8, 23, 77, 281, \ldots</math>
| <math>O(N^{4/3})</math>
| Sedgewick, 1986
|----
| <math>9(4^{k-1}-2^{k-1})+1, 4^{k+1}-6\cdot2^k+1</math>
| <math>1, 5, 19, 41, 109, \ldots</math>
| <math>O(N^{4/3})</math>
| Sedgewick, 1986
|----
| <math>h_k = \max\left\{\left\lfloor 5h_{k-1}/11 \right\rfloor, 1\right\}, h_0 = N</math>
| <math>\left\lfloor \frac{5N}{11} \right\rfloor, \left\lfloor \frac{5}{11}\left\lfloor \frac{5N}{11} \right\rfloor\right\rfloor, \ldots, 1</math>
| ?
| [[Gaston Gonnet|Gonnet]] & [[Ricardo Baeza-Yates|-{Baeza-Yates}-]], 1991
|----
| <math>\left\lceil \frac{9^k-4^k}{5\cdot4^{k-1}} \right\rceil</math>
| <math>1, 4, 9, 20, 46, 103, \ldots</math>
| ?
| Tokuda, 1992
|----
| unknown
| <math>1, 4, 10, 23, 57, 132, 301, 701</math>
| ?
| Ciura, 2001
|}

Kada binarna reprezentacija broja ''N'' sadrži mnogo uzastopnih nula, Šelsort, koristeći originalnu Šelovu sekvencu, ima Θ(''N''<sup>2</sup>) poređenja u najgorem slučaju. Na primer, ovaj slučaj se javlja kada je ''N'' stepen dvojke, kada elementi veći i manji od medijane zauzmu nemaprne i parne pozicije redom, jer se porede tek u poslednjoj iteraciji.

Gonnet i Baeza-Yates su zaključili da Šelsort u proseku koristi najmanje poređenja kada je odnos uzastopnih raskoraka blizak 2.2. Zbog toga su se njihova sekvenca sa odnosom 2.2 i Tokudina sekvenca sa odnosom 2.25 pokazale efikasnim. Međutim, nije poznato zašto je tako. Sedgewick predlaže raskorake koji imaju nizak [[Највећи заједнички делилац]] ili su uzajamno prosti.

Imajući u vidu prosečan broj poređenja, najbolje poznate sekvence gapova su 1, 4, 10, 23, 57, 132, 301, 701 i slične. Ovi raskoraci su dobijeni empirijski. Optimalni raskoraci veći od 701 ostaju nepoznati, ali dobri rezultati se dobijaju nastavljanjem ove sekvence po formuli <math>h_k = \lfloor 2.25 h_{k-1} \rfloor</math>.

Tokudina sekvenca, definisana formulom <math>h_k = \lceil h'_k \rceil</math>, where <math>h'_k = 2.25 h'_{k-1} + 1</math>, <math>h'_1 = 1</math>, se preporučuje u praksi.

== Složenost ==

Važi sledeća osobina: nakon ''h''<sub>2</sub>-sortiranja bilo kog ''h''<sub>1</sub>-sortiranog niza, niz ostaje ''h''<sub>1</sub>-sortiran. Svaki ''h''<sub>1</sub>-sortirani i ''h''<sub>2</sub>-sortirani niz je takođe i (''a''<sub>1</sub>''h''<sub>1</sub>+''a''<sub>2</sub>''h''<sub>2</sub>)-sortiran, za svako nenegativno celobrojno ''a''<sub>1</sub> i
''a''<sub>2</sub>. Zbog ovoga je složenost Šelsorta u najgorem slučaju vezana za [[Problem novčića]]: za date uzajamno proste brojeve ''h''<sub>1</sub>,..., ''h''<sub>''n''</sub>, Frobenijev broj ''g''(''h''<sub>1</sub>,..., ''h''<sub>''n''</sub>) je najveći celi broj koji se ne može predstaviti kao ''a''<sub>1</sub>''h''<sub>1</sub>+ ... +''a''<sub>''n''</sub>''h''<sub>''n''</sub> sa nenegativnim celim brojevima ''a''<sub>1</sub>,..., ''a''<sub>''n''</sub>. Koristeći poznatu formulu za ovaj problem, možemo odrediti složnost Šelsorta u najgorem slučaju za neke klase sekvenci raskoraka.

Kada su raskoraci stepeni dvojke, Espelid je izračunao da da je prosečan broj operacija <math>0.5349N\sqrt{N}-0.4387N-0.097\sqrt{N}+O(1)</math>. [[Donald Knut]] je odredio prosečnu složenost sortiranja niza od ''N'' elemenata koristeći dva raskoraka (''h'', 1) koja iznosi <math>2N^2/h + \sqrt{\pi N^3 h}</math>. Sledi da Šelsort sa dva prolaska, gde je ''h'' = Θ(''N''<sup>1/3</sup>), u proseku koristi ''O''(''N''<sup>5/3</sup>) poređenja. [[Ендру Јау]] je odredio prosečnu složenost Šelsorta sa tri prolaska. Njegov rezultat su preradili Janson i Knut. Prosečan broj poređenja pri korišćenju tri raskoraka (''ch'', ''cg'', 1), gde su ''h'' i ''g'' uzajamno prosti, je <math>\frac{N^2}{4ch}+O(N)</math> u prvom, <math>\frac{1}{8g}\sqrt{\frac{\pi}{ch}}(h-1)N^{3/2}+O(hN)</math> u drugom i <math>\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^2g^3h^2)</math> u trećem prolasku. ''ψ''(''h'', ''g''), koje se pojavljuje u poslednjoj formuli, je funkcija aproskimativno jednaka <math>\sqrt{\frac{\pi h}{128}}g + O(g^{-1/2}h^{1/2}) + O(gh^{-1/2})</math>. Kada je ''h'' = Θ(''N''<sup>7/15</sup>) i ''g'' = Θ(''h''<sup>1/5</sup>), prosečno vreme sortiranja je ''O''(''N''<sup>23/15</sup>).

Na osnovu eksperimenata, smatra se da se Šelsort sa Hibbardovim i Knutovim sekvencama raskoraka izvršava u ''O''(''N''<sup>5/4</sup>)
vremenu u proseku, i da Gonnet i Baeza-Yates-ova sekvenca zahtevaju 0.41''N''ln''N''(ln ln''N''+1/6) premeštanja elemenata u proseku. Aproksimacije prosečnog broja operacija ranije datih sekvenca nisu uspele za nizove sa preko milion elemenata.

Sledeći graf pokazuje prosečan broj poređenja elemenata za različite varijante Šelsorta. Vrednosti su podeljene teoretskom donjom granicom log<sub>2</sub>''N''!. Sekvenca 1, 4, 10, 23, 57, 132, 301, 701 je produžena služeći se formulom <math>h_k = \lfloor2.25 h_{k-1}\rfloor</math>.

[[Датотека:Shell sort average number of comparisons (English).svg|центар]]

Prema [[Kolmogoroljevoj složenosti]], dokazano je da je donja granica za prosečan broj operacija pri ''m'' prolazaka u Šelsortu: Ω(''mN''<sup>1+1/''m''</sup>) kada je ''m''≤log<sub>2</sub>''N'' i Ω(''mN'') when ''m''>log<sub>2</sub>''N''. Prema tome, Šelsort ima mogućnost da u proseku ima O(''N''log''N'') složenost samo kada koristi sekvence raskoraka kojima broj raskoraka raste proporcionalno logaritmu veličine niza. Međutim, nije poznato da li Šelsort može zaista da dostigne ovu složenost, koja je optimalna za sortiranje poređenjem.

Prema Plaxtonu, Poonenu i Suelu, složenost algoritma u najgorem slučaju je Ω(''N''(log''N''/log log''N'')<sup>2</sup>).

== Primena ==

Šelsort se retko koristi u praksi. Vrši više operacija i koristi više [[Кеш централне процесорске јединице|keš memorije procesora]] od [[Квиксорт|Kviksorta]]. Međutim, kako se može lako implementirati i kako ne koristi [[stek prostor]], neke implementacije [[qsort]] fukcije u C biblioteci je koriste. Na primer, Šelsort se koristi u [[uClibc]] biblioteci. Iz sličnih razloga, implementiran je i u [[Језгро линукса|Linuks krenelu]].

== Reference ==
{{reflist}}

== Literatura ==
* {{Cite book | ref= harv|last=Knuth|first=Donald E. |title=The Art of Computer Programming. Volume 3: Sorting and Searching |edition=2nd |publisher=Addison-Wesley |location=Reading, Massachusetts |year=1997|chapter=Shell's method|isbn=978-0-201-89685-5|pages=83–95}}
* [http://www.cs.princeton.edu/~rs/shell/ -{Analysis of Shellsort and Related Algorithms], Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.}-
{{refend}}

== Spoljašnje veze ==
* [http://xlinux.nist.gov/dads/HTML/shellsort.html -{Shellsort}-]

{{normativna kontrola}}

[[Категорија:Алгоритми сортирања]]
[[Категорија:Сортирање поређењем]]