Shellsort

Из Википедије, слободне енциклопедије
Shellsort
Step-by-step visualisation of Shellsort
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

Š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.[1][2] 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, soriraju se elementi na udaljenosti 5, odnosno soritaju se podnitovi (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10).

Na primer, podniz (a1, a6, a11) se od (62, 17, 25) transofmiše u (17, 25, 62). U sledećem prolazu vrši se 3-sortiranje na podnizovima (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). U poslednjem prolazu 1-sortiranje je uobičajeno sortiranje umetanjem nad celim nizom (a1,..., a12).

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\le 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\ge(5/2)^{q+1},
\forall p\colon0\le p<q\Rightarrow\gcd(a_p,n)=1\}
1, 3, 7, 21, 48, 112, \ldots O(N e^\sqrt{8\ln(5/2)\ln N}) Incerpi & Sedgewick, 1985
4^k + 3\cdot2^{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\cdot2^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\cdot4^{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 Θ(N2) 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.25 h_{k-1} \rfloor.

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

Složenost[уреди]

Važi sledeća osobina: nakon h2-sortiranja bilo kog h1-sortiranog niza, niz ostaje h1-sortiran. Svaki h1-sortirani i h2-sortirani niz je takođe i (a1h1+a2h2)-sortiran, za svako nenegativno celobrojno a1 i a2. Zbog ovoga je složenost Šelsorta u najgorem slučaju vezana za Problem novčića: za date uzajamno proste brojeve h1,..., hn, Frobenijev broj g(h1,..., hn) je najveći celi broj koji se ne može predstaviti kao a1h1+ ... +anhn sa nenegativnim celim brojevima a1,..., an. 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 = Θ(N1/3), u proseku koristi O(N5/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^2g^3h^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 = Θ(N7/15) i g = Θ(h1/5), prosečno vreme sortiranja je O(N23/15).

Na osnovu eksperimenata, smatra se da se Šelsort sa Hibbardovim i Knutovim sekvencama raskoraka izvršava u O(N5/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 log2N!. Sekvenca 1, 4, 10, 23, 57, 132, 301, 701 je produžena služeći se formulom h_k = \lfloor2.25 h_{k-1}\rfloor.

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: Ω(mN1+1/m) kada je m≤log2N i Ω(mN) when m>log2N. 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)2).

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[уреди]

  1. ^ Shell, D.L. (1959). „A High-Speed Sorting Procedure“. Communications of the ACM 2 (7): 30–32. DOI:10.1145/368370.368387. 
  2. ^ 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 „Shell sort“. National Institute of Standards and Technology Приступљено 17. 7. 2007.. 

Референце[уреди]

Literatura[уреди]

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

Spoljašnje veze[уреди]