Metode de sortare

Shell Sort [inserare]


Cazul mediu : -

Cazul defavorabil : O(N * log^2 N)

Memorie folosita : O(1)

Stabil : NU

Descriere :

Algoritmul shell sort este o generalizare a algoritmului insertion sort. La algoritmul insertion 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 salt s1 mai mare decât 1. Asta înseamnă că fiecare element din şirul iniţial este deplasat spre stânga cu câte s1 poziţii atât timp cât întâlneşte 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 se face cu saltul 1. Această ultimă iteraţie este practic un insetion sort clasic.Principiul este că după fiecare iteraţie şirul devine din ce în ce “mai sortat”. Iar cum algoritmul insertion sort funcţionează cu atât mai repede cu cât şirul este mai sortat, per ansamblu vom obţine o îmbunătăţire de viteză.