SORTAREA PRIN INSERTIE

Sortarea prin inserare seamană cu sortarea prin selecţie. Tabloul este împărţit imaginar în două parţi :o parte sortată şi o parte nesortată. La început, partea sortată conţine primul element al tabloului şi partea nesortată conţine restul tabloului. La fiecare pas, algoritmul ia primul element din partea nesortată şi îl inserează în locul potrivit al părţii sortate. Când partea nesortată nu mai are nici un element, algoritmul se opreşte.

Exemplu

Să sortăm şirul {9, -5, 2, 12, 4} folosind sortarea prin inserţie.

9, -5, 2, 12, 4 nesortat

9, -5, 2, 12, 4 -5 va fi inserat 9 > -5 , interschimbăm

-5, 9, 2, 12, 4 2 va fi inserat 9 > 2, interschimbăm

-5, 2, 9, 12, 4 -5 < 2 , 2 nu se face interschimbare

-5, 2, 9, 12, 4 12 va fi inserat 9 < 12 nu se face interschimbare

-5, 2, 9, 12, 4 4 va fi inserat, 4 < 12, interschimbăm

-5, 2, 9, 4, 12 4 < 9 , interschimbăm

-5, 2, 4, 9, 12 sortat

Algoritm descris în pseudocod

pentru i ← 1,n execută

j← i ;

cât timp j>0 si v[j-1]>v[j] execută

aux ← v[j] ;

v[j] ← v[j-1] ;

v[j-1] ← aux ;

j ← j-1 ;

sfcât timp

sfpentru

Implementare C++

void sortareInserţie(int v[ ], int n)

{

int i,j,aux;

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

{

j=i;

while (j>0 && v[j-1]>v[j])

{

aux=v[j];

v[j]=v[j-1];

v[j-1]=aux;

j--;

}

}}