Šelo rikiavimo algoritmas

Šelo algoritmas () – 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.

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 N3/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 masyvams efektyvumas neišryškėja. Šelo metodo tikėtinas sudėtingumas yra O(N1.2), kas yra žymiai geriau už O(N²). Pavyzdžiui, jei N yra 128, tai O(N1.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 

Kategorija:Rikiavimo algoritmai