Propunem studierea următorilor algoritmi de sortare:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort

Numim sortare orice aşezare(sau - mai clar - reaşezare) a unor elemente date în aşa fel încât, după aşezare, să existe o ordine completă în funcţie de un atribut(numit cheie) al elementelor.

Pentru a exista o ordine completă, trebuie să alegem o relaţie pe care vrem sa o impunem. Dacă relaţia este valabilă între oricare două elemente pentru care primul element este aşezat la stânga celui de-al doilea, atunci avem o ordine completă.

Exemplu: dacă alegem drept cheie un atribut număr întreg şi relaţia mai mic sau egal(⇐), obţinem ordinea crescătoare.

Vom descrie un algoritm de sortare prin:

• timp mediu - timpul de execuţie la care ne aşteptăm, în medie, pentru sortare
• timp la limită- timpul de execuţie pentru cel mai rău caz posibil
• memorie - memoria maximă de care are nevoie algoritmul pentru sortare(excludem memoria deja alocată înainte de algoritm → vectorul efectiv ce va fi sortat)
• stabilitate - un algoritm stabil păstrează ordinea în care apar două elemente cu aceeaşi cheie(atributul după care sortăm)

Folosim notaţia O(n) pentru a indica:

• un număr de operaţii de ordinul lui n. În acest caz, spunem că avem „complexitate de timp de ordinul lui n“
• o dimensiune de ordinul n pentru memoria alocată. În acest caz, spunem că avem „complexitate de spaţiu de ordinul lui n“

Fiecare algoritm se bazează pe o metodă de sortare:

• Bubble sort - interschimbare
• Selection sort - selecţie
• Insertion sort - inserare
• Merge sort - interclasare
• Quick sort - partiţionare

• timp mediu: O(N^2)
• timp la limită: O(N^2)
• memorie: O(1)
• Stabil: DA

• timp mediu: O(N^2)
• timp la limită: O(N^2)
• memorie: O(1)
• Stabil: DA

• timp mediu: O(N^2)
• timp la limită: O(N^2)
• memorie: O(1)
• Stabil: DA

• timp mediu: O(N log N)
• timp la limită: O(N log N)
• memorie: O(N)
• Stabil: DA

• timp mediu: O(N log N)
• timp la limită: O(N^2)
• memorie: O(log N)
• Stabil: NU