Sortarea prin insertie cu diminuarea incrementului
- La
inceput, toate articolele care sunt despartite prin cate 4 pozitii, sunt grupate
si sortate separat prin metoda insertiei.
- Acest proces se
numeste sortare-4.
- In exemplul din fig.324,
unde se sorteaza 8 elemente,
s-au format 4 grupe de elemente separate prin cate 4 pozitii.
- Dupa aceasta
prima trecere, se formeaza grupuri in care elementele sunt
separate prin cate doua
pozitii si din nou sunt sortate prin insertie.
- Acest proces se
numeste sortare-2.
- In final, la cea de-a treia
trecere, elementele sunt sortate obisnuit (sortare-1).
- Se precizeaza faptul
ca fiecare k-sortare
este de fapt o sortare prin insertie la care pasul este k
(nu 1 ca la insertia normala).
34 65
12 22 83 18 04 67
sortare-4
34 18 04 22 83 65 12 67
sortare-2
04 18 12 22 34 65 83 67
sortare-1
04 12 18 22 34 65 67 83
Fig. 3.2.4. Sortare prin
insertie cu diminuarea incrementului
- Desi la prima vedere
aceasta metoda care presupune cateva treceri asupra tuturor
elementelor, nu pare foarte performanta, totusi la o
analiza mai atenta, fiecare trecere realizeaza relativ
putine modificari ale pozitiilor elementelor.
- Este evident ca metoda
conduce la sortarea elementelor si ca fiecare pas profita
de cei anteriori (fiecare sortare-i combina grupuri deja sortate-j).
- Este posibila orice
secventa de incrementi atata timp cat ultimul este egal cu
unitatea: in cel mai rau caz in acest pas se va realiza in intregime
procesul de sortare.
- Este mai putin evident,
dar practica demonstreaza ca o secventa de
incrementi descrescatori care nu sunt puteri ale lui 2 asigura o eficienta
superioara procesului de sortare.
- Analiza metodei shellsort.
Analiza acestui algoritm pune probleme deosebite din punct de vedere
matematic, multe din ele inca nerezolvate.
- In particular, nu se cunoaste nici
macar secventa de incrementi cea mai potrivita. Ceea
ce este deosebit de interesant este faptul ca incrementii nu trebuie sa fie unii
multiplii altora.
- Pentru o eficienta sporita a
sortarii este de dorit ca intre diferitele lanturi de parcurgere
sa aiba loc cat mai multe interactiuni.
- De asemenea este valabila urmatoarea
teorema pe care de fapt se
bazeaza metoda.
- Daca o secventa sortata-k este sortata-i ea ramane si sortata-k.
- Cu alte cuvinte, procesul de sortare cu
diminuarea incrementului este cumulativ.
.com