Sortarea prin inserție
Când primești cărți de joc una câte una, o pui pe fiecare la locul ei printre cele din mână: o muți spre stânga până găsește o carte mai mică. Asta e sortarea prin inserție. E O(n²) în cel mai rău caz, dar foarte rapidă pe liste aproape sortate, motiv pentru care Python o folosește în interiorul propriei sortări.
Ideea
Lista se împarte în două: în stânga, partea deja sortată, în dreapta restul. La fiecare pas iei primul element din dreapta (cheie) și îl inserezi în partea sortată, deplasând spre dreapta toate elementele mai mari decât el.
Scrie funcția sortare_insertie(lista) care sortează crescător o copie a listei prin inserție și returnează (sortata, deplasari), unde deplasari este numărul de mutări a[j + 1] = a[j]. Nu folosi sort() sau sorted().
- Pentru fiecare i de la 1, salvează cheia și deplasează spre dreapta elementele mai mari decât ea, numărând deplasările.
- Pune cheia în golul rămas.
- Trebuie să apară: ([1, 2, 3, 4], 6), ([1, 2, 3, 4], 1), ([1, 2, 5, 5, 6, 9], 6), ([7], 0).
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan