Sortarea prin inserareDescriere
Sortarea prin inserare seamană oarecum cu sortarea prin selecţie. Tabloul este impă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.
9 -5 2 12 4
ExempluSă sortăm şirul {9, -5, 2, 12, 4} folosind sortarea prin inserţie.
9 -5 2 12 4
9 > -5 , interschimbăm
-5 9 2 12 4
9 > 2, interschimbăm
-5 2 9 12 4
-5 < 2 , nu se face interschimbare
-5 2 9 12 4
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 ;