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 ;