Корисник:Zdravko Lukić/песак

Sortiranje po Šelu (eng.Shellsort) уреди

Sortiranje po Šelu (eng.Shellsort) je takav algoritam za sortiranje niza da prolazi kroz niz više puta, da bi pri svakom prolazu vršio zamenu elemenata koji su udaljeni jedan od drugog. Generalno to je sortiranje elemenata slično sortiranju umetanjem (eng. insertion sort) ili sortiranje zamenom susednih elemenata (eng. bubble-sort). Nedostatak sortiranja zamenom susednih elemenata je što elemenat sa velikom vrednošću, a malom vrednošću indeksa putuje vrlo sporo na svoje mesto. Zamisao Donalda Šela (eng. Donald Shell)1959. godine je da se sortiranje zamenom susednih elemenata mođe ubrzati na način da se upoređuju elementi na većem razmaku (a ne na susednom), te da se napredovanjem algoritma taj razmak postepeno smanjuje, kako bi se na kraju upoređivali susedni elementi.

Opis уреди

Sortiranje po Šelu je jednostavno proširenje sortiranja umetanjem koje dopušta direktnu razmenu udaljenih elemenata.Proširenje se sastoji u tome da se kroz algoritam umetanja prolazi više puta, u prvom prolazu, umesto koraka 1 uzima se neki korak h koji je manji od koraka n (što omogućava razmenu udaljenih elemenata) i tako se dobija n-sortiran niz tj. niz u kome su elementi na rastojanju h sortirani, mada susedni elementi to ne moraju biti.U drugom prolazu kroz isti algoritam sprovodi se isti postupak ali za manji korak h. Sa prolazima nastavlja sve do korak h=1, u kome se dobija potpuno sortirani niz. Primer kako radi sortiranje po Šelu u 5,3 i 1 koraku pokazan je dole:

${\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{unos elemenata:}}&62&83&18&53&07&17&95&86&47&69&25&28\\{\hbox{posle peto-sortiranja:}}&17&28&18&47&07&25&83&86&53&69&62&95\\{\hbox{ posle treće-sortiranja:}}&17&07&18&47&28&25&69&62&53&83&86&95\\{\hbox{posle prvo-sortiranja:}}&07&17&18&25&28&47&53&62&69&83&86&95\\\end{array}}$

U prvom prolazu ili peto-sortiranju algoritam je razdvojio niz u pet podnizova(peto-sortiranje) (a₁, a₆, a₁₁), (a₂, a₇, a₁₂),(a₃, a₈), (a₄, a₉), (a₅, a₁₀).Na primer, zamenio je podniz (a₁, a₆, a₁₁) od niza (62, 17, 25) u niz (17, 25, 62).Znači u podnizu je sortirao brojeve i tako je urađeno u svakom od pet podnizova.U sledećem prolazu algoritam je razdvojio niz u tri podniza (a₁, a₄, a₇, a₁₀),(a₂, a₅, a₈, a₁₁), (a₃, a₆, a₉, a₁₂).I u poslednjem prolazu algoritam je sredio niz po redu (a₁,..., a₁₂). Na ovaj način sortiranje je mnogo efikasnije.

Pseudokod уреди

Koristeći Marcin Ciura sekvencu sa unutrašnjim umetanjem sortiranja.

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (gap in gaps)
    # Do an insertion sort for each gap size.
    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

Kod u programskom jeziku C уреди

Kod je rađen u programskom jeziku C. Bira brojeve nasumično, a potom ih sortira.

#include <cstdlib>
#include <iostream>
#include <time.h>
 
using namespace std;
 
void print_niz(int *niz, int velicina) {
    for (int i=0; i<velicina; i++) {
        printf("%d",niz[i]);
    }
    printf("\n");
}
 
void shell_sort(int *niz, int velicina) {
    int skok = velicina/2;
    while (skok > 0) {
        for (int i=skok; i<velicina; i++) {
            for (int j=i; j>0; j=j-skok) {
                if(niz[j] < niz[j-1]){
                    int temp = niz[j];
                    niz[j] = niz[j-1];
                    niz[j-1] = temp;
                }
                else {
                    break;
                }
            }
        }        
        skok = skok/2;
    }
}
 
int main(int argc, char** argv) {
 
    srand((unsigned)time(0));
     
    int velicina = 10;
    int *niz = new int[velicina];
     
    for (int i=0; i<velicina; i++) {
        niz[i] = rand()%10+1;
    }
    print_niz(niz, velicina);
    shell_sort(niz, velicina);
    print_niz(niz, velicina);
	system ("PAUSE");
     
    return 0;
}

Sekvenca уреди

Svaka sekvenca koja sadrži 1 daje ispravno sortiranje, međutim, osobine tako dobijenih verzija sortiranja po Šelu mogu biti veoma različiti. Tabela poredi većinu predloženih sekvenci objavljenih do sada.Neke od njih imaju smanjenje elementata koji zavise od veličine sortiranog niza (N).

opšta funkcija (k ≥ 1)	Koncentracija razmaka	Najgori slučaj vremenske zamršenosti	Autor i godina objavljivanja
$\lfloor N/2^{k}\rfloor$	$\left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1$	$\Theta (N^{2})$ [kada je N=2^p]	Donald 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, 1960Frank, R.M.; Lazarus, R.B. (1960). „A High-Speed Sorting Procedure”. Communications of the ACM. 3 (1): 20—22. doi:10.1145/366947.366957.
$2^{k}-1$	$1,3,7,15,31,63,\ldots$	$\Theta (N^{3/2})$	Hibbard, 1963Hibbard, Thomas N. (1963). „An Empirical Study of Minimal Storage Sorting”. Communications of the ACM. 6 (5): 206—213. doi:10.1145/366552.366557.
$2^{k}+1$ , sa 1 pripremljenim	$1,3,5,9,17,33,65,\ldots$	$\Theta (N^{3/2})$	Papernov & Stasevich, 1965Papernov, A.A.; Stasevich, G.V. (1965). „A Method of Information Sorting in Computer Memories” (PDF). Problems of Information Transmission. 1 (3): 63—75.
uzastopni brojevi obrazaca $2^{p}3^{q}$	$1,2,3,4,6,8,9,12,\ldots$	$\Theta (N\log ^{2}N)$	Pratt, 1971Pratt, Vaughan Ronald (1979). Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences). Garland. ISBN 0-8240-4406-1.
$(3^{k}-1)/2$ , nije veća od $\lceil N/3\rceil$	$1,4,13,40,121,\ldots$	$\Theta (N^{3/2})$	Knuth, 1973Knuth, Donald E. (1997). „Shell's method”. The Art of Computer Programming. Volume 3: Sorting and Searching (2nd изд.). Reading, Massachusetts: Addison-Wesley. стр. 83—95. ISBN 0-201-89685-0.
$\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 & Robert Sedgewick (computer scientist), 1985Incerpi, Janet; Sedgewick, Robert (1985). „Improved Upper Bounds on Shellsort”. Journal of Computer and System Sciences. 31 (2): 210—224.
$4^{k}+3\cdot 2^{k-1}+1$ , sa 1 pripremljenim	$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, 1986Sedgewick, Robert (1986). „A New Upper Bound for Shellsort”. Journal of Algorithms. 7 (2): 159—173. doi:10.1016/0196-6774(86)90001-5.
$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 & Ricardo Baeza-Yates, 1991Gonnet, Gaston H.; Baeza-Yates, Ricardo (1991). „Shellsort”. Handbook of Algorithms and Data Structures: In Pascal and C (2nd изд.). Reading, Massachusetts: Addison-Wesley. стр. 161—163. ISBN 0-201-41607-7.
$\left\lceil {\frac {9^{k}-4^{k}}{5\cdot 4^{k-1}}}\right\rceil$	$1,4,9,20,46,103,\ldots$	?	Tokuda, 1992Tokuda, Naoyuki (1992). „An Improved Shellsort”. Ур.: van Leeuven, Jan. Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture. Amsterdam: North-Holland Publishing Co. стр. 449—457. ISBN 0-444-89747-X.
nepoznat	$1,4,10,23,57,132,301,701$	?	Ciura, 2001Ciura, Marcin (2001). „Best Increments for the Average Case of Shellsort”. Ур.: Freiwalds, Rusins. Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (PDF). London: Springer-Verlag. стр. 106—117. ISBN 3-540-42487-3.

Aplikacije уреди

Sortiranje po Šelu se sada retko koristi u ozbiljnim aplikacijama.Ona obavlja više operacija i ima veći promašaj odnosa keša od brzog sortiranja (eng.qsort).Međutim, može biti implementiran koristeći mali kod i ne koristi strukturu podataka koja skladišti informacije o aktivnim potprocedurama računarskog programa.Sortiranje po Šelu može se pozvati u programskom jeziku C iz uClibc biblioteke.Sortiranje po Šelu može se takođe servirati kao pod algoritam introspektivnog sortiranja, (eng. introspective sort), kako bi sortirao kratke podnizove i sprečio usporavanje kada rekurziona dubina prevazilazi dati limit.Ovaj princip se koristi, na primer, kod bzip2 kompresije.