Šelsort
Šelsort () 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 () 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.

{| class="wikitable"
|- style="background-color: #efefef;"
! General term (k ≥ 1)
! Concrete gaps
! Worst-casetime complexity
! Author 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 .

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

Literatura 
 
 -{Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.}-

Spoljašnje veze 
 -{Shellsort}-

Алгоритми сортирања
Сортирање поређењем
Šelsort ( ) 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 godine . Vreme izvršavanja ovog algoritma zavisi od sekvenca raskoraka ( ) 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 vrednostigarantuje sortitan niz na kraju izvršavanja algoritma . Ispod je dat primer izvršavanja Šelsorta , sa raskoracimai U prvom prolasku , sortiraju se elementi na udaljenosti odnosno soritaju se podnizovi ( a1 , a6 , a11 ) , ( a2 , a7 , a12 ) , ( a3 , a8 ) , ( a4 , a9 ) , ( a5 , a10 ) . Na primer , podniz ( a1 , a6 , a11 ) se odtransofmiše u U sledećem prolazu vrši sesortiranje na podnizovima ( a1 , a4 , a7 , a10 ) , ( a2 , a5 , a8 , a11 ) , ( a3 , a6 , a9 , a12 ) . U poslednjem prolazusortiranje 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 , foreach ( gap in gaps ) { # Uraditi sortiranje umetanjem za svaku gap veličinu. for ( i = gap ; i < n ; i += { 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 vrednostgarantuje 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 ≥ ! Concrete gaps ! Worst-casetime complexity ! Author and year of publication |---- | | | [ when N=2p ] | Shell , |---- | | | | Frank & Lazarus , |---- | | | | Hibbard , |---- | , prefixed with 1 | | | Papernov & Stasevich , |---- | successive numbers of the form | | | Pratt , |---- | , not greater than | | | Knuth , |---- | | | | Incerpi & Sedgewick , |---- | , prefixed with 1 | | | Sedgewick , |---- | | | | Sedgewick , |---- | | | ? | Gonnet & -{ Baeza-Yates }- , |---- | | | ? | Tokuda , |---- | unknown | | ? | Ciura , | } 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 blizak2 . Zbog toga su se njihova sekvenca sa odnosom2 i Tokudina sekvenca sa odnosom25 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 sui slične . Ovi raskoraci su dobijeni empirijski . Optimalni raskoraci veći odostaju 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,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 , 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 zahtevaju41NlnN( 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 !. Sekvencaje produžena služeći se formulom \ . 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 Literatura -{ Analysis of Shellsort and Related Algorithms , Robert Sedgewick , Fourth European Symposium on Algorithms , Barcelona , September }- Spoljašnje veze -{ Shellsort }- Алгоритми сортирања Сортирање поређењем