Š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 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Shell_sorting_algorithm_color_bars.svg/220px-Shell_sorting_algorithm_color_bars.svg.png)
Š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.
U prvom prolasku, sortiraju se elementi na udaljenosti 5, odnosno soritaju se podnizovi (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 complexityAuthor and year of publication [when N=2p] Shell, 1959 Frank & Lazarus, 1960 Hibbard, 1963 , prefixed with 1 Papernov & Stasevich, 1965 successive numbers of the form Pratt, 1971 , not greater than Knuth, 1973 Incerpi & Sedgewick, 1985 , prefixed with 1 Sedgewick, 1986 Sedgewick, 1986 ? Gonnet & Baeza-Yates, 1991 ? Tokuda, 1992 unknown ? 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 .
Tokudina sekvenca, definisana formulom , where , , 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 . Donald Knut je odredio prosečnu složenost sortiranja niza od N elemenata koristeći dva raskoraka (h, 1) koja iznosi . 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 u prvom, u drugom i u trećem prolasku. ψ(h, g), koje se pojavljuje u poslednjoj formuli, je funkcija aproskimativno jednaka . 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 .
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Shell_sort_average_number_of_comparisons_%28English%29.svg/512px-Shell_sort_average_number_of_comparisons_%28English%29.svg.png)
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
- ^ Shell, D.L. (1959). „A High-Speed Sorting Procedure” (PDF). Communications of the ACM. 2 (7): 30—32. doi:10.1145/368370.368387. Архивирано из оригинала (PDF) 30. 08. 2017. г. Приступљено 08. 01. 2014.
- ^ 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 изд.). 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