Sortarea prin insertie.

Search:

Algoritmi.

Prezentarea algoritmului de sortare prin insertie (insertion sort).

Alege:
1. Despre sortarea prin insertie.
2. Implementarea algoritmului de sortare prin insertie in Pascal.
3. Implementarea algoritmului de sortare prin insertie in C.
4. Comportarea eficienta sau ineficienta.
5. Compararea principiului sortarii prin insertie cu principiul sortarii prin selectie.

1. Sortarea prin insertie. >>>

Sortarea prin insertie este un algoritm simplu de sortare prin compararea unor elemente (chei) aflate in tablouri de date sortate,contruind cate o intrare la un anumit timp.Acest tip de algoritm este mai putin eficient in lucrul cu liste mari de date, si nu are performanta algoritmilor de sortare avansati cum sunt algoritmul de sortare rapida (quick sort),heap sort sau merge sort, insa prezinta diverse avantaje:

* Este simplu de implementat;
* Se comporta eficient in lucrul cu liste mici de date;

* Este eficient in setari de date partial sortate:practica in timp O(n+d) miscari de inversiuni,unde d este numarul de inversiuni;

* Este mult mai eficient din punct de vedere practic in comparatie cu algoritmii O(n²) cum ar fii sortarea prin selectie sau bubble sort;

* Timpul mediu de sortare este n²/4 fiind liniar in cele mai bune cazuri;

* Este un algoritm stabil(nu schimba ordinea relativa a elementelor cu aceeasi cheie;

* Poate cere direct un amanunt constant O(1) aflat intr-un spati de memorie extern.

Algorimul sortarii prin insertie.

In termeni abstracti, fiecare iteratie a unei insertii schimba un element din datele de intrare introduse si o insereaza la pozitia corectaintr-o lista sortata in prealabil, acest procedeu repetandu-se cu fiecare elemet introdus.Alegerea elementului ce urmeaza a fii luat din datele de intrare este arbitrara, si poate fii facuta folosind aproape orice algoritm de cautare in tablouri.
Tabloul sortat, care rezulta dupa un numar de k iteratii contine primele k intrari ale tabloului de intrare.In fiecare segventa de sortare, prima data de intrare este sortata, comparata si apoi inserata ca si rezultat in partea dreapta a tabloului de date, la locul potrivit:

Scopul de a crea o metoda numita "insertie" presupune a insera o valoare intr-o segventa de sortare la inceputul unui tablou de date.
Aceasta se desfasoara de la inceputul pana la sfarsitul segventei de sortare si schimba fiecare element al unei pozitii catre dreapta pana cand se gaseste locul potrivit pentru noul element.Executia sortarii prin insertie incepe de la capatul din stanga al unui tablou si invoca insertia fiecarui element gasit in locatia potrivita.Ordinea segventei cu care se face inserarea este amplasata la inceputul tabloului in locatia index-ilor sortati in prealabil.Fiecare insertie inscrie o singura valoare.

2. Implementarea algoritmului de selectie prin insertie in Pascal: >>>
Tabloul este vazut ca fiind format din doua subtablouri a[1], a[2],..., a[i-1] si respectiv a[i], a[i+1],...,a[N] (i=2,N).Secventa a[1],...,a[i-1] este ordonata si urmeaza ca a[i] sa fie inserat in aceasta secventa la locul potrivit, astfel incit secventa a[1],...,a[i-1],a[i] sa devina ordonata, urmind ca in pasul urmator cele doua subtablouri considerate sa fie a[1],...,a[i] si a[i+1],...,a[N].
Pentru a gasi locul in care trebuie sa fie inserat a[i] se parcurge sirul a[1],...,a[i-1] de la dreapta spre stinga, pina cind fie se gaseste un element cu cheia <= a[i].cheie, fie s-a atins capatul sirului.Aici se poate utiliza metoda fanionului, extinzind tabloul spre stinga cu elementul a[0] care se asigneaza initial cu a[i] (deci TipIndex=0..N).

procedure Insertie;
VAR i,j : TipIndex;
beginfor i:=2 to N do begin 
{ insereaza a[i] la locul
potrivit in sirul 
 a[1]...a[i]} 
 a[0]:=a[i]; j:=i-1;
{ cauta locul de inserare }
while a[j].cheie > a[0].cheie do begina[j+1]:=a[j]; j:=j-1;
end;
a[j+1]:=a[0];
end;
end; {Insertie}

Principiu: reprezinta o varianta a sortarii prin insertie, in care cautarea locului de inserare se face aplicind cautarea binara, stiind ca secventa a[1],...,a[i-1] este deja ordonata.

Implementarea algoritmului in Pascal:

procedure InsertieBinara;
VAR i,j,s,d,m : TipIndex; x : TipElement;
beginfor i:=2 to N do beginx:=a[i]; s:=1; d:=i-1;
while s<=d do beginm:=(s+d) div 2;
if a[m].cheie > x.cheie then d:=m-1
else s:=m+1
end;
for j:=i-1 downto s do a[j+1]:=a[j];
a[s]:=x
end
end; {InsertieBinara}

3. Implementarea algoritmului de sortare prin insertie in limbajul C. >>>

#include 
/* Se sorteaza un tablou de numere intregi */
void sortare_insertie(int a[], int length)
{int i;
for (i=0; i < length; i++)
{/* Se insereaza elementul a[i] intr-o sub-list sortata */
int j, v = a[i];
for (j = i - 1; j >= 0; j--)
{if (a[j] <= v) break;
a[j + 1] = a[j];
}
a[j + 1] = v; 
}
}
void VerificaDacaTabloulEsteSortat(int array[], int length)
{int i;
for (i = 1; i < length; i+=1)
{if (array[i-1] > array[i])
{printf("\nTabloul nu este sortat la pozitia %d", i-1);
}
}
}
int main(void)
{unsigned int i;
int a[] = {5,1,9,3,2};
sortare_insertie(a, sizeof(a)/sizeof(*a));
/* Se afiseaza elementele tabloului a */
for(i=0; i{printf("%d\n", a[i]);
}VerificaDacaTabloulEsteSortat(a, sizeof(a)/sizeof(*a));
return 0;
}

In cadrul acestei metode, C este de ordinul N*log N, iar M de N*N. Se obtin valori minime ale lui C pentru tablouri ordonate invers si valori maxime pentru tablouri ordonate.

4. Comportare eficienta sau ineficienta a sortarii prin insertie. >>>
In cele mai bune cazuri de comportare ale unui tablou de date sortat in prealabil, aceasta implementare a sortarii pein insertie se executa intr-un timp de O(n): pentru ca in fiecare iteratie, primul furnizat la intrare si care a ramas nesortat este comparat numai cu ultimul element aflat in subsectiunea tabloului in care sunt inserate elementele sortate. Cel mai ineficient caz de comportare al metodei de sortatare prin insertie este in cazul in care se lucreaza cu un tabloul sortat in ordine descrescatoare, astfel incat fiecare executie a buclei de sortare verifica si schimba intreaga sectiune a tabloului inainte de inserarea unui element urmator.

5. O comparatie dintre principiul sortarii prin insertie si cel de sortare prin selectie. >>>
Sortarea prin insertie este foarte asemanatoare cu sortarea cu sortarea prin selectie.Asemeni ca si in sortarea prin selectie, dupa un numar de k parcurgeri ale tabloului, primele k elemente sunt sortate in ordine crescatoare.In cazul sortarii prin selectie, aceste k elemente reprezinta elementele care au cele mai mici valori, insa in cadrul sortarii prin insertie ele reprezinta primele k elemente aflate in tabloul care trebuie sortat.Avantajul sortarii prin insertie este acela ca se vor verifica mai multe elemente decat este necesar pentru a insera in ordine un element k+1, comparativ cu sortarea prin selectie unde trebuie sa verifice toate elementele ramase nesortate pentru a gasii cel mai mic element.

Inapoi la pagina principala