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

Sortarea prin metoda bulelor se consideră drept una din cele mai puţin efective metode de sortare, dar cu un algoritm mai simplu.

• Ideea de bază a sortării prin metoda bulelor este în a parcurge tabloul, de la stânga spre dreapta,

fiind comparate elementele alăturate a[i] si a[i+1]. Dacă vor fi găsite 2 elemente neordonate, valorile lor vor fi interschimbate.

• Parcurgerea tabloului de la stânga spre dreapta se va repeta atât timp cât vor fi întâlnite

elemente neordonate.

//sortare descrescatoare
void bubble(int a[],int n)
{
	int i,schimbat,aux;
	do
	{
		schimbat = 0;
		for(i = 0; i < n-1; i++) //parcurgem vectorul
		if(a[i] < a[i+1]) //daca valoarea i din vectorul a este
		//mai mica decat cea de pe pozitia i+1
		{ //interschimbare
			aux = a[i];
			a[i] = a[i+1];
			a[i+1] = aux;
			schimbat = 1;
		}
	}while(schimbat);
}

• 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