Šelo rikiavimo algoritmas

Algoritmas
Tipas	Rikiavimo algoritmai
Pavadinimas	Šelo (Shell Sort)
Sudėtingumas	Vidutinis - o(N^1,2); blogiausias - O(N²)
Greitos nuorodos	Algoritmai Rikiavimo algoritmai Šelo Šablonas

Šelo algoritmas (angl. shellsort) – vienas iš seniausiai naudojamų rikiavimo algoritmų (sukurtas 1959 Donaldo L. Šelo), vienodai efektyviai dirbantis, nepriklausomai nuo duomenų ypatumų, taigi tinkamas tais atvejais, kai šie ypatumai nėra žinomi.

Šelo algoritmas gali būti nagrinėjamas kaip burbulo rikiavimo arba įterpimo metodo bendrasis atvejis.^[1]

Duomenų seka interpretuojama kaip h-surikiuota (nuo bet kurios vietos imant kiekvieną h-ąjį elementą, gaunamas surikiuotas posekis). Algoritmo vykdymo efektyvumas priklauso nuo skaičiaus h kitimo dėsnio parinkimo ir nuo duomenų sekos.

Esant h kitimo dėsniui 3·h+1 (1, 4, 13, 40, 121, ..), algoritmui reikia ne daugiau nei N^3/2 lyginimų.

Šelo ir burbuliuko metodų palyginimas

Šelo rikiavimo algoritmas išsprendžia vieną iš problemų, kylančių naudojant burbuliuko metodą, t. y.: didelės reikšmės greitai juda į savo vietas, o mažos - lėtai. Tai rikiavimo keitimu (exchange sort) metodas, kur atliekamos serijos palyginimų ir keitimų. Tarp lyginamų elementų yra fiksuotas atstumas („gap“). Pradinis atstumas dažniausiai imamas lygus pusei masyvo elementų. Kai su einamuoju atstumu nebeatliekama daugiau pakeitimų, jis mažinamas per pusę. Šis procesas tęsiamas, kol atstumas pasidaro 1 ir nebepakeičiama nė viena pora elementų.

Šelo rikiavimo algoritmas (pseudokodas)

nustatyti pradinį Atstumą lygų pusei rikiuojamo masyvo elementų
REPEAT
   REPEAT
      FOR elementams nuo pirmo iki elementų skaičius minus Atstumas DO
         IF einamasis ir elementas nutolęs einamuoju atstumu yra bloga tvarka
            THEN sukeisti juos vietomis
   UNTIL nebuvo atlikta pakeitimų
     sumažinti Atstumą dvigubai
UNTIL Atstumas yra mažesnis už 1

Iš esmės Šelo metodas atlieka rikiavimą burbuliuko metodu ir lygina elementus nutolusius einamuoju atstumu, kol atliekamas burbuliuko rikiavimas su žingsniu 1. Šelo metodas efektyvesnis už surikiuotą paieška (selection sort), burbuliuko ir rikiavimo įterpimu (insertion sort) metodus atsitiktiniams masyvams, ypač, jei jie dideli. Mažiems masyvas efektyvumas neišryškėja. Šelo metodo tikėtinas sudėtingumas yra O(N^1.2), kas yra žymiai geriau už O(N²). Pavyzdžiui, jei N yra 128, tai O(N^1.2)=337.8, o O(N²)=16384. Taigi kuo didesnis masyvas rikiuojamas, tuo Šelo metodas efektyvesnis už burbuliuko (1000 elementų masyvui apie 10 kartų).

Pavyzdys

Tarkime, kad turime duomenų seką, kurią reikia surikiuoti:

3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2

Pirmiausiai įsivaizduojame, kad tai lentelė su 7 stulpeliais, tada kiekvieną stulpelį atskirai surikiuojame:

3 7 9 0 5 1 6          3 3 2 0 5 1 5
8 4 2 0 6 1 5    ->    7 4 4 0 6 1 6
7 3 4 9 8 2            8 7 9 9 8 2

Kitame žingsnyje žiūrime į duomenis kaip į tris stulpelius, kuriuos vėl atskirai surikiuojame:

3 3 2          0 0 1
0 5 1          1 2 2
5 7 4          3 3 4
4 0 6    ->    4 5 6
1 6 8          5 6 8
7 9 9          7 7 9
8 2            8 9

Po šio žingsnio seka beveik pilnai surikiuota, taigi rikiuojant seką kaip vieną stulpelį, tik tris elementus (6, 8, 9) reikia šiek tiek perkelti.

Realizacija Java kalba:

void shellsort (int[] a, int n)
{
    int i, j, k, h, t;
    int[] stulp = { 1,3,7,31,92,259,815,1968,4711,11969,27901,84801,
                    213331,543749,1355339,3501671,8810089,21521774,
                    58548857,157840433,410151271,1131376761,2147483647 };
    for (k=0; stulp[k]<n; k++);
    while (--k >= 0)
    {   h=stulp[k];
        for (i=h; i<n; i++)
        {   t=a[i];
            j=i;
            while (j>=h && a[j-h]>t)
            {   a[j]=a[j-h];
                j=j-h;
            }
            a[j]=t;
        }
    }
}

Šaltiniai

↑ Knuth, Donald E. (1997). „Shell's method“. The Art of Computer Programming. Volume 3: Sorting and Searching (2nd leid.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 978-0-201-89685-5.

Šiame straipsnyje naudojami diskutuotini terminai.
Daugiau apie kompiuterinius terminus skaitykite žodynėlyje.

[1] Knuth, Donald E. (1997). „Shell's method“. The Art of Computer Programming. Volume 3: Sorting and Searching (2nd leid.). Reading, Massachusetts: Addison-Wesley. pp. 83–95. ISBN 978-0-201-89685-5.

[1]