1. Selection Sort
Algoritmul de sortare prin selecție selectează cel mai mic (sau cel mai mare, în funcție de ordinea dorită) element din lista nesortată și îl plasează la începutul listei. Apoi, se repetă procesul pentru sublistă.
Caracteristici:
•Complexitatea: O(n²) în cazuri generale, O(n) în cazuri favorabile (când lista este deja parțial sortată).
•Stabilitate: Stabil, adică nu modifică ordinea elementelor cu valori egale.
•Avantaje: Ușor de implementat și eficient pentru liste mici sau aproape sortate.
Secvență algoritm în C++:
int n, X[100];
//citire X[] cu n elemente
for(int i = 0 ; i < n - 1 ; i ++)
for(int j =i + 1 ; j < n ; j ++)
if(X[i] > X[j])
{
int aux = X[i];
X[i] = X[j];
X[j] = aux;
}
2. Insertion Sort
este un algoritm simplu care presupune parcurgerea listei și inserarea fiecărui element în poziția corectă față de celelalte elemente deja sortate.
Caracteristici:
Complexitatea: O(n²) în cazuri generale, O(n) în cazuri favorabile (când lista este deja parțial sortată).
Stabilitate: Stabil, adică nu modifică ordinea elementelor cu valori egale.
Avantaje: Ușor de implementat și eficient pentru liste mici sau aproape sortate.
Secvență algoritm în C++:
void sortarePrinInserție(int lista[], int lungime) {
for (int i = 1; i < lungime; i++) {
int elementCurent = lista[i];
int j = i - 1;
while (j >= 0 && lista[j] > elementCurent) {
lista[j + 1] = lista[j]; j--;
} lista[j + 1] = elementCurent;
}
}
3.Bubble Sort
Sortarea prin bule presupune compararea a două elemente adiacente și schimbarea lor dacă sunt într-o ordine greșită. Acest proces se repetă până când întreaga listă este sortată.
Caracteristici:
•Complexitatea: O(n²) în cazul mediu și cel mai rău, dar poate fi O(n) dacă lista este deja sortată.
•Stabilitate: Stabil.
•Avantaje: Ușor de înțeles și implementat, dar ineficient pentru liste mari.
Secvență algoritm în C++:
void bubble(int a[],int n)
{
int i,schimbat,aux;
do {
schimbat = 0;
for(i = 0; i < n-1; i++) {
if (a[i] < a[i+1]) {
aux = a[i];
a[i] = a[i+1];
a[i+1] = aux;
schimbat = 1;
}
}
} while(schimbat);
}
Prezentarea metodelor de sortare:
4. Quick Sort
Sortarea rapida este un algoritm eficient bazat pe diviziune și cucerire. Alegem un pivot și împărțim lista în două subliste: una cu elemente mai mici decât pivotul și alta cu elemente mai mari. Apoi aplicăm recursiv aceleași proceduri pentru fiecare sublistă.
Caracteristici:
•Complexitatea: O(n log n) în medie, O(n²) în cazuri defavorabile.
•Stabilitate: Instabil.
•Avantaje: Foarte eficient pentru liste mari.
Secvență algoritm în C++:
void QuickSort(int v[], int st, int dr)
{ if(st < dr)
{ int m = (st + dr) / 2;
int aux = v[st];
v[st] = v[m];
v[m] = aux;
int i = st , j = dr, d = 0;
while(i < j)
{ if(v[i] > v[j])
{ aux = v[i];
v[i] = v[j];
v[j] = aux;
d = 1 - d;}
i += d;
j -= 1 - d;}
QuickSort(v, st , i - 1);
QuickSort(v, i + 1 , dr);}}
5. Merge Sort
Merge Sort este un algoritm eficient de tip „divide et impera”. Acesta împarte lista în subliste mai mici și le fuzionează într-o manieră ordonată.
Caracteristici:
•Complexitatea: O(n log n) în toate cazurile.
•Stabilitate: Stabil.
•Avantaje: Performanță constantă, eficient pentru liste mari și date externe.
Secvență algoritm în C++:
void MergeSort(int v[], int st, int dr)
{ if(st < dr)
{ int m = (st + dr) / 2;
MergeSort(v, st , m);
MergeSort(v, m + 1 , dr);
int i = st, j = m + 1, k = 0;
while( i <= m && j <= dr )
if( v[i] < v[j])
tmp[++k] = v[i++];
else
tmp[++k] = v[j++];
while(i <= m)
tmp[++k] = v[i++];
while(j <= dr)
tmp[++k] = v[j++];
for(i = st , j = 1 ; i <= dr ; i ++ , j ++)
v[i] = tmp[j]; }}