Algoritmi de Sortare în C++

De ce sunt importanți?

Algoritmii de sortare sunt fundamentali în informatică și apar frecvent la BAC și olimpiade.

1. Bubble Sort (Sortare prin Interschimbare)

Cel mai simplu algoritm de sortare.

Copiază
1void bubbleSort(int v[], int n) {
2    for (int i = 0; i < n - 1; i++) {
3        for (int j = 0; j < n - i - 1; j++) {
4            if (v[j] > v[j + 1]) {
5                // Interschimbă
6                int aux = v[j];
7                v[j] = v[j + 1];
8                v[j + 1] = aux;
9            }
10        }
11    }
12}

Complexitate: O(n²)

2. Selection Sort (Sortare prin Selecție)

Găsește minimul și îl pune pe prima poziție, apoi repetă.

Copiază
1void selectionSort(int v[], int n) {
2    for (int i = 0; i < n - 1; i++) {
3        int pozMin = i;
4        for (int j = i + 1; j < n; j++) {
5            if (v[j] < v[pozMin]) {
6                pozMin = j;
7            }
8        }
9        // Interschimbă v[i] cu v[pozMin]
10        int aux = v[i];
11        v[i] = v[pozMin];
12        v[pozMin] = aux;
13    }
14}

Complexitate: O(n²)

3. Insertion Sort (Sortare prin Inserție)

Inserează fiecare element în poziția corectă.

Copiază
1void insertionSort(int v[], int n) {
2    for (int i = 1; i < n; i++) {
3        int key = v[i];
4        int j = i - 1;
5        
6        while (j >= 0 && v[j] > key) {
7            v[j + 1] = v[j];
8            j--;
9        }
10        v[j + 1] = key;
11    }
12}

Complexitate: O(n²), dar O(n) pentru vectori aproape sortați

4. Folosind sort() din STL (Recomandat)

Copiază
1#include <algorithm>
2
3int v[100], n;
4
5// Sortare crescătoare
6sort(v, v + n);
7
8// Sortare descrescătoare
9sort(v, v + n, greater<int>());

Complexitate: O(n log n)

Comparație

Exerciții BAC

1. •Sortează descrescător folosind Bubble Sort
2. •Afișează primele 3 cele mai mari elemente
3. •Sortează doar elementele pare
4. •Interclasează doi vectori sortați

---

Găsește un profesor de informatică pentru pregătire BAC intensivă!