12.1.7 Sortarea prin metoda ShellCazul mediu : -Cazul defavorabil : O(N * log^2 N)Memorie folosita : O(1)Stabil : NUSortare descrescatoare : j >= h && a[j-h] < vSortare crescatoare : j >= h && a[j-h] > v

Metoda Shell a fost descoperită de către Donald L. Shell. Metoda porneşte de la analiza critică a metodei bulelor. în metoda bulelor, se compară elementele vecine, şi, dacă nu sunt în ordinea cerută, atunci ele se permută. De aceea, elementele care nu sunt în ordine corectă se deplasează cu o singură poziţie. Pentru a îmbunătăţi acest procedeu, ar trebui să realizăm deplasări cu mai multe locuri ale elementelor, la o permutare a lor. Acest lucru se poate realiza dacă în loc de a compara elemente învecinate, comparăm elemente aflate la o anumită distanţă între ele. în cazul în care ele nu sunt în ordinea cerută, ele se vor permuta. în felul acesta elementele se deplasează făcând salturi mai mari decât o poziţie. Distanţa dintre elementele comparate se numeşte increment.La fiecare permutare a două valori, algoritmul compară valoarea mai mică permutată cu cea precedentă (poziţia precedentă se stabileşte folosind incrementul) şi realizează o nouă permutare dacă este nevoie.Această comparaţie se continuă, propagându-se spre începutul şirului, până când:a. nu se mai fac permutări; saub. nu mai există elemente în şir (se ajunge la un element care nu mai are precedent în şir). Incrementul se micşorează după o parcurgere a şirului de clemente care se sortează şi se reia parcurgerea de la începutul şirului. De aici rezultă denumirea de sortare cu micşorarea incrementului.

Eficienţa metodei Shell este mult mai mare în comparaţie cu metoda bulelor în cazul în care se sortează un număr mai mare de date (de ordinul sutelor sau miilor).O influenţă asupra eficienţei metodei o are şi modul în care se alege incrementul. S-a arătat că valorile incrementului la diferite parcurgeri ale şirului de sortat este bine să fie numere prime între ele. în capitolul de faţă ne mărginim la alegerea incrementului iniţial egal cu n/2, unde n este numărul elementelor şirului de sortat. De asemenea, după fiecare parcurgere a şirului, acesta se va înjumătăţi. Cazul cel mai nefavorabil al acestei metode se obţine când n este o putere a lui doi. Acest caz se poate evita dacă la fiecare parcurgere a şirului incrementul se determină prin relaţia:____________________increment = increment/2 + 1. dacă increment > 2._________________________

Metoda de sortare Shell poate fi definită astfel:c. inc = n/2, unde prin n am notat numărul elementelor care se sortează.d. Se realizează o parcurgere a şirului de elemente care se sortează. Aceasta implică următorii paşi:

d. i = inc. j = i-inc+1.d. Dacă j>0 şi elementele de ordine j şi j+inc nu satisfac criteriul de ordonare, atunci elementele respective se permută. Altfel se continuă cu pasul 2.6.d. j = j-inc.d. Se reia de la pasul 2.3.d. i = i+1.2.7. Dacă i > n, se termină parcurgerea curentă a şirului. Altfel se reia de la pasul 2.

e. inc = inc/2.f. Dacă inc > 0. atunci se reia de la pasul 2. Altfel şirul este sortat.

Paşii 2.4 şi 2.5 se realizează în cazul în care s-a efectuat permutarea elementelor de ordinul j şi j+inc. în acest caz se permută, dacă este necesar, elementele precedenteelementului deplasat în poziţia j. Elementele precedente sunt: j-inc, j-2*inc.........................Aceasta serealizează repetând pasul 2.3 atât timp cât j > 0 şi se fac permutări.

În 1959 D.L. Shell a propus un algoritm de sortare bazat pe metoda prin inserţie directă, algoritm cu o performanţă îmbunătăţită deoarece face comparaţii între chei mai distanţate din vector. Algoritmul sortează mai întâi prin inserţie subvectori obţinuţi din vectorul iniţial prin extragerea componentelor aflate la o distanţă h una de cealaltă, distanţă care se numeşte increment. Repetând procedeul pentru incremenţi din ce în ce mai mici şi, în final, pentru incrementul 1, se obţine vectorul sortat.

• se consideră un şir descrescător de numere naturale, numite incremenţi dintre care ultimul, ht, este 1:

– _________h1 > h2 > … > hi > hi+1 > … > ht = 1.

• (1) Se porneşte cu incrementul h1.

• (2) La pasul iterativ m se consideră incrementul hm . Se sortează prin inserţie directă subvectorii obţinuţi din vectorul iniţal luând elemente aflate la distanţa hm, adică subvectorii:

• A[1], A[hm+1], A[2hm+1], …

• A[2], A[hm+2], …

•

în continuare este prezentat un mic exemplu, sortare folosind şi metoda Shell.ExempluNr componente vector:7. înainte de ordonare:****** SORT SHELL ******Interschimbare element 0 cu 3, increment 3Interschimbare element 1 cu 4, increment 3Interschimbare element 2 cu 5, increment 3Interschimbare element 3 cu 6, increment 3Interschimbare element 0 cu 1, increment 1Interschimbare element 1 cu 2, increment 1Interschimbare element 3 cu 4, increment 1Interschimbare element 2 cu 3, increment 1Interschimbare element 4 cu 5, increment 1Interschimbare element 3 cu 4, increment 1După ordonare SHELL: v

== 6 17 30 32 40 45

v = 46 30 32 40 6 17 45

40 30 32 46 6 17 45 40 6 32 46 30 17 45 40 6 17 46 30 32 45 40 6 17 45 30 32 46 6 40 17 45 30 32 46 6 17 40 45 30 32 466 17 40 30 45 32 466 17 30 40 45 32 46 6 17 30 40 32 45 46 6 17 30 32 40 45 46

• A[hm], A[2hm], …

• Apoi se reia pasul (2) pentru incrementul hm+1.

• Deoarece ultimul increment este ht=1, ultimul pas iterativ t se reduce la sortarea prin inserţie directă, deci vectorul va fi sortat.

• D. E. Knuth recomandă incremenţi obţinuţi cu următoarele formule recursive:

• şi , , avem 1, 4, 13, 40,…

• şi , , avem 1, 3, 15, 31,…

• _______________Există o estimare a complexităţii acestui algoritm care-l plasează în clasa O(n1,3) ,din punct de vedere al numărului de comparaţii. Din punct de vedere al spaţiului, am văzut că el necesită h(1) locaţii suplimentare pentru componentele marcaj, cu ajutorul cărora eliminăm testele de nedepăşire a dimensiunii, teste care ar dubla numărul de comparaţii.

 

Shell SortCazul mediu : -Cazul defavorabil : O(N * log^2 N)Memorie folosita : O(1)Stabil : NUSortare descrescatoare : j >= h && a[j-h] < vSortare crescatoare : j >= h && a[j-h] > vDescriere :Algoritmul shell sort este o generalizare a algoritmului insertion sort. La algoritmulinsertion sort, pentru a insera un nou element în lista de elemente deja sortate, se deplaseazăfiecare element cu câte o poziţie spre dreapta atât timp cât avem elemente mai mari decât el.Practic fiecare element înaintează spre poziţia sa finală cu câte o poziţie.Algoritmul shell sort lucrează similar, doar că deplasează elementele spre poziţia finală cumai mult de o poziţie. Se lucrează în iteraţii. În prima iteraţie se aplică un insertion sort cu salts1 mai mare decât 1. Asta înseamnă că fiecare element din sirul iniţial este deplasat spre stângacu câte s1 poziţii atât timp cât întâlneste elemente mai mari decât el.Se repetă asemenea iteraţii cu salturi din ce în ce mai mici s2, s3, s4, etc. Ultima iteraţie seface cu saltul 1. Această ultimă iteraţie este practic un insetion sort clasic.Principiul este că după fiecare iteraţie sirul devine din ce în ce “mai sortat”. Iar cumalgoritmul insertion sort funcţionează cu atât mai repede cu cât sirul este mai sortat, per

ansamblu vom obţine o îmbunătăţire de viteză.Implementare :void shell(long a[],long n){long i, j, k, h, v;long cols[] = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,1968, 861, 336, 112, 48, 21, 7, 3, 1};for (k = 0; k < 16; k++) //parcurgem fiecare limita{h = cols[k];for (i = h; i < n; i++) //insertion sort{v = a[i];j = i;while (j >= h && a[j-h] > v) //crescator{a[j] = a[j-h];j = j - h;}a[j] = v;

}}