Metode de sortare

Insertion Sort [inserare]


Cazul mediu : O(N^2)

Cazul defavorabil : O(N^2)

Memorie folosita : O(1)

Stabil : DA

Descriere :

Spre deosebire de alți algoritmi de sortare, sortarea prin inserție este folosită destul de des pentru sortarea tablourilor cu număr mic de elemente. De exemplu, poate fi folosit pentru a îmbunătăți rutina de sortare rapidă.Sortarea prin inserție seamănă oarecum cu sortarea prin selecție. Tabloul este împarțit imaginar în doua părți - o parte sortată și o parte nesortată. La început, partea sortată conține primul element al tabloului si partea nesortată conține restul tabloului. La fiecare pas,algoritmul ia primul element din partea nesortată și il inserează în locul potrivit al parții sortate. Când partea nesortată nu mai are nici un element, algoritmul se oprește.