SORTAREA PRIN INSERȚIE CU PAS VARIABIL

Unul dintre principalele dezavantaje ale sortării prin inserţie este faptul că la fiecare etapă un element al şirului se mută cu o singură poziţie. O variantă de scădere a numărului de operaţii efectuate este de a compara elemente aflate la o distanţă mai mare (h ≥ 1) şi de a realiza mutarea acestor elemente peste mai multe poziţii. Un şir x[1..n] este considerat h -sortat dacă orice subşir x[i₀],x[i₀ + h],x[i₀ + 2h]... este sortat (i₀ ∈ {1,...,h}). Aceasta este ideea algoritmului propus de Donald Shell în 1959 și este cunoscut sub numele ”shell sort”.

Elementul esențial al algoritmului îl reprezintă alegerea valorilor pasului h.

Exemplu:

Se da un şir cu 15 elemente. Pentru următoarele valori ale pasului: h=13, h=4, h=1 (care corespund unui şir h_k dat prin relaţia h_k =3h_k-1 +1, h₁ =1):

Etapa 1:

Pentru h=13 se aplică algoritmul sortării prin inserţie subşirurilor x[1], x[14] şi x[2], x[15], singurele subşiruri cu elemente aflate la distanţa h care au mai mult de un element:

Tabloul: 14 8 10 7 9 12 5 15 2 13 6 1 4 3 11

Indici: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Şi se obţine:

Tabloul: 3 8 10 7 9 12 5 15 2 13 6 1 4 14 11

Indici: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Etapa 2:

Pentru h=4 se aplică algoritmul sortării prin inserţie succesiv subşirurilor: x[1], x[5], x[9], x[13], x[2],x[6],x[10],x[14],x[3],x[7],x[11],x[15],x[4],x[8],x[12].

După prima subetapă (prelucrarea primu­lui subşir) prin care se ordonează subşirul constituit din elementele marcate:

Tabloul: 3 8 10 7 9 12 5 15 2 13 6 1 4 14 11

se obţine:

Tabloul: 2 8 10 7 3 12 5 15 4 13 6 1 9 14 11

La a doua subetapă se aplică sortarea prin inserţie asupra subşirului constituit din elementele marcate

Tabloul: 2 8 10 7 3 12 5 15 4 13 6 1 9 14 11

obţinându-se aceeaşi configuraţie (subşirul este deja ordonat crescător) din care se prelucrează acum subşirul constituit din elementele marcate:

Tabloul: 2 8 10 7 3 12 5 15 4 13 6 1 9 14 11

Obtinandu-se:

Tabloul: 2 8 5 7 3 12 6 15 4 13 10 1 9 14 11

Se aplică acum sortarea prin inserţie asupra subşirului constituit din elementele marcate:

Tabloul: 2 8 5 7 3 12 6 15 4 13 10 1 9 14 11

obţinându-se:

Tabloul: 2 8 5 1 3 12 6 7 4 13 10 15 9 14 11

Se aplică acum sortarea prin inserţie asupra întregului şir.

Algoritm descris în pseudocod

h←1

cât timp h<n execută

h←h*3 + 1;

sfcât timp

cât timp h≥1execută

h←[h / 3]

pentru i←h,n xecută x←v[i] j←i

cât timp v[j-h]>x execută

v[j]←v[j-h] j←j-h

sfcât timp

v[j]←x

sfpentru

sfcât timp

Implementare în C++

void shellSort(int v[],int n)

{

int i,j,h,x;

h=1;

while(h<n)

h=h*3 + 1;

while(h>=1)

{

h=h / 3;

for(i=h;i<n;i++)

{

x=v[i];j=i;

while(v[j-h]>x)

{

v[j]=v[j-h];

j=j-h;

if(j<h) break;

};

v[j]=x;

}

}

}