Šelo rikiavimo algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Š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 yra įterpimo metodo modifikacija.

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 rikiavimo (Shell sort) algoritmas išsprendžia vieną iš problemų, 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(N1.2), kas yra žymiai geriau už O(N2). Pavyzdžiui, jei N yra 128, tai O(N1.2)=337.8, o O(N2)=16384. Taigi kuo didesnis masyvas rikiuojamas, tuo Šelo metodas efektyvesnis už burbuliuko (1000 elementų masyvui apie 10 kartų).

[taisyti] 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ą stuplpelį, 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;
        }
    }
} 

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