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--;
}
}}