Šelsort

Š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) 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. Vreme izvršavanja ovog algoritma zavisi od sekvenca raskoraka (engl. 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 hti 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.

${\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}}$

U prvom prolasku, sortiraju se elementi na udaljenosti 5, odnosno soritaju se podnizovi (a₁, a₆, a₁₁), (a₂, a₇, a₁₂), (a₃, a₈), (a₄, a₉), (a₅, a₁₀).

Na primer, podniz (a₁, a₆, a₁₁) se od (62, 17, 25) transofmiše u (17, 25, 62). U sledećem prolazu vrši se 3-sortiranje na podnizovima (a₁, a₄, a₇, a₁₀), (a₂, a₅, a₈, a₁₁), (a₃, a₆, a₉, a₁₂). U poslednjem prolazu 1-sortiranje je uobičajeno sortiranje umetanjem nad celim nizom (a₁,..., a₁₂).

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.

General term (k ≥ 1)	Concrete gaps	Worst-case time complexity	Author and year of publication
$\lfloor N/2^{k}\rfloor$	$\left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1$	$\Theta (N^{2})$ [when N=2p]	Shell, 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})$	Frank & Lazarus, 1960
$2^{k}-1$	$1,3,7,15,31,63,\ldots$	$\Theta (N^{3/2})$	Hibbard, 1963
$2^{k} 1$, prefixed with 1	$1,3,5,9,17,33,65,\ldots$	$\Theta (N^{3/2})$	Papernov & Stasevich, 1965
successive numbers of the form $2^{p}3^{q}$	$1,2,3,4,6,8,9,12,\ldots$	$\Theta (N\log ^{2}N)$	Pratt, 1971
$(3^{k}-1)/2$, not greater than $\lceil N/3\rceil$	$1,4,13,40,121,\ldots$	$\Theta (N^{3/2})$	Knuth, 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}})$	Incerpi & Sedgewick, 1985
$4^{k} 3\cdot 2^{k-1} 1$, prefixed with 1	$1,8,23,77,281,\ldots$	$O(N^{4/3})$	Sedgewick, 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})$	Sedgewick, 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$	?	Gonnet & Baeza-Yates, 1991
$\left\lceil {\frac {9^{k}-4^{k}}{5\cdot 4^{k-1}}}\right\rceil$	$1,4,9,20,46,103,\ldots$	?	Tokuda, 1992
unknown	$1,4,10,23,57,132,301,701$	?	Ciura, 2001

Kada binarna reprezentacija broja N sadrži mnogo uzastopnih nula, Šelsort, koristeći originalnu Šelovu sekvencu, ima Θ(N²) 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 $h_{k}=\lfloor 2.25h_{k-1}\rfloor$.

Tokudina sekvenca, definisana formulom $h_{k}=\lceil h'_{k}\rceil$, where $h'_{k}=2.25h'_{k-1} 1$, $h'_{1}=1$, se preporučuje u praksi.

Složenost

Važi sledeća osobina: nakon h₂-sortiranja bilo kog h₁-sortiranog niza, niz ostaje h₁-sortiran. Svaki h₁-sortirani i h₂-sortirani niz je takođe i (a₁h₁ a₂h₂)-sortiran, za svako nenegativno celobrojno a₁ i a₂. Zbog ovoga je složenost Šelsorta u najgorem slučaju vezana za Problem novčića: za date uzajamno proste brojeve h₁,..., h_n, Frobenijev broj g(h₁,..., h_n) je najveći celi broj koji se ne može predstaviti kao a₁h₁ ... a_nh_n sa nenegativnim celim brojevima a₁,..., a_n. 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 $0.5349N{\sqrt {N}}-0.4387N-0.097{\sqrt {N}} O(1)$. Donald Knut je odredio prosečnu složenost sortiranja niza od N elemenata koristeći dva raskoraka (h, 1) koja iznosi $2N^{2}/h {\sqrt {\pi N^{3}h}}$. Sledi da Šelsort sa dva prolaska, gde je h = Θ(N^1/3), u proseku koristi O(N^5/3) 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 ${\frac {N^{2}}{4ch}} O(N)$ u prvom, ${\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2} O(hN)$ u drugom i $\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})$ u trećem prolasku. ψ(h, g), koje se pojavljuje u poslednjoj formuli, je funkcija aproskimativno jednaka ${\sqrt {\frac {\pi h}{128}}}g O(g^{-1/2}h^{1/2}) O(gh^{-1/2})$. Kada je h = Θ(N^7/15) i g = Θ(h^1/5), prosečno vreme sortiranja je O(N^23/15).

Na osnovu eksperimenata, smatra se da se Šelsort sa Hibbardovim i Knutovim sekvencama raskoraka izvršava u O(N^5/4) vremenu u proseku, i da Gonnet i Baeza-Yates-ova sekvenca zahtevaju 0.41NlnN(ln lnN 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₂N!. Sekvenca 1, 4, 10, 23, 57, 132, 301, 701 je produžena služeći se formulom $h_{k}=\lfloor 2.25h_{k-1}\rfloor$.

Prema Kolmogoroljevoj složenosti, dokazano je da je donja granica za prosečan broj operacija pri m prolazaka u Šelsortu: Ω(mN^{1 1/m}) kada je m≤log₂N i Ω(mN) when m>log₂N. Prema tome, Šelsort ima mogućnost da u proseku ima O(NlogN) 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(logN/log logN)²).

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.

Literatura

• Knuth, Donald E. (1997). „Shell's method”. The Art of Computer Programming. Volume 3: Sorting and Searching (2nd изд.). Reading, Massachusetts: Addison-Wesley. стр. 83—95. ISBN 978-0-201-89685-5. 
• Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.

Spoljašnje veze

• Shellsort