Algoritmi de sortare în C++: teorie și exemple practice esențiale pentru examen

Sortarea pare un subiect plictisitor până înțelegi că e peste tot: liste de elevi după medie, produse după preț, scoruri într-un joc. La Bacul de informatică, algoritmii de sortare apar constant, fie direct, fie ascunși într-o problemă mai mare. Hai să-i înțelegi pe bune, nu să-i memorezi pe de rost.

De ce contează sortarea

A sorta înseamnă să rearanjezi elementele unei colecții într-o anumită ordine — crescătoare sau descrescătoare. Sună banal, dar e una dintre cele mai studiate probleme din informatică, fiindcă apare constant și fiindcă te învață să gândești în termeni de complexitate: câte operații face algoritmul tău în funcție de mărimea datelor.

La examen nu ai nevoie doar să scrii cod care funcționează, ci să înțelegi de ce un algoritm e mai rapid decât altul. Asta separă un răspuns bun de unul memorat.

Bubble sort: cel mai simplu de înțeles

Bubble sort compară perechi vecine și le interschimbă dacă sunt în ordine greșită. La fiecare trecere prin vector, cel mai mare element "se ridică" la dreapta, ca o bulă în apă.

#include <iostream>
using namespace std;

void bubbleSort(int v[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool schimbat = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (v[j] > v[j + 1]) {
                swap(v[j], v[j + 1]);
                schimbat = true;
            }
        }
        // dacă nu am schimbat nimic, vectorul e deja sortat
        if (!schimbat) break;
    }
}

int main() {
    int v[] = {5, 2, 9, 1, 7};
    int n = 5;
    bubbleSort(v, n);
    for (int i = 0; i < n; i++) cout << v[i] << " ";
    return 0;
}

Observă variabila schimbat: dacă o trecere completă nu produce nicio interschimbare, vectorul e deja sortat și ne oprim. E o optimizare mică, dar arată că ai înțeles ce se întâmplă. Bubble sort e lent (O(n²)), dar e perfect ca să prinzi ideea de comparare și interschimbare.

Selection sort: alege minimul

Selection sort parcurge vectorul și, la fiecare pas, caută cel mai mic element din partea nesortată, apoi îl mută la locul lui.

void selectionSort(int v[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int indexMin = i;
        for (int j = i + 1; j < n; j++) {
            if (v[j] < v[indexMin]) {
                indexMin = j;
            }
        }
        swap(v[i], v[indexMin]);
    }
}

Diferența față de bubble sort: aici faci puține interschimbări (cel mult una pe pas), dar tot atâtea comparații. Tot O(n²), însă util când mutarea elementelor e costisitoare.

Insertion sort: cum îți aranjezi cărțile de joc

Gândește-te cum îți aranjezi cărțile în mână: iei câte una și o pui la locul potrivit printre cele deja ordonate. Exact asta face insertion sort.

void insertionSort(int v[], int n) {
    for (int i = 1; i < n; i++) {
        int valoare = v[i];
        int j = i - 1;
        // deplasăm la dreapta elementele mai mari decât valoarea
        while (j >= 0 && v[j] > valoare) {
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = valoare;
    }
}

Insertion sort e tot O(n²) în cazul cel mai rău, dar are un avantaj real: pe date aproape sortate ajunge la O(n). Dacă vectorul e deja ordonat, bucla while nici nu pornește. De aceea e folosit des ca optimizare pe subliste mici, în interiorul altor algoritmi.

Quicksort și mergesort: ideea de "divide et impera"

Cei trei algoritmi de mai sus sunt simpli, dar lenți pe date multe. Pentru viteză reală intervin algoritmii care împart problema în bucăți mai mici (divide et impera).

Quicksort alege un element numit pivot, apoi rearanjează vectorul astfel încât valorile mai mici stau în stânga pivotului, iar cele mai mari în dreapta. Apoi repetă procesul, recursiv, pe fiecare jumătate.

void quickSort(int v[], int st, int dr) {
    if (st >= dr) return;
    int pivot = v[(st + dr) / 2];
    int i = st, j = dr;
    while (i <= j) {
        while (v[i] < pivot) i++;
        while (v[j] > pivot) j--;
        if (i <= j) {
            swap(v[i], v[j]);
            i++;
            j--;
        }
    }
    quickSort(v, st, j);
    quickSort(v, i, dr);
}

Mergesort împarte vectorul în două jumătăți, le sortează separat (recursiv), apoi le interclasează într-un singur vector ordonat. Ideea de interclasare e cheia: ai doi vectori deja sortați și îi combini parcurgându-i în paralel, alegând mereu elementul mai mic.

Ambii ating o complexitate medie de O(n log n) — mult mai bine decât O(n²). Diferența: quicksort e de obicei mai rapid în practică și nu folosește memorie suplimentară, dar are un caz nefericit O(n²) dacă pivotul e ales prost. Mergesort e stabil și garantează O(n log n), dar consumă memorie în plus.

Tabel de complexități: ce alegi și când

Iată comparația pe care merită să o ții minte pentru examen:

Algoritm	Cel mai bun caz	Caz mediu	Cel mai rău caz	Memorie extra	Stabil
Bubble sort	O(n)	O(n²)	O(n²)	O(1)	Da
Selection sort	O(n²)	O(n²)	O(n²)	O(1)	Nu
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Da
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	Nu
Mergesort	O(n log n)	O(n log n)	O(n log n)	O(n)	Da

Cum citești tabelul în practică:

• Date puține sau aproape sortate — insertion sort e excelent.
• Vrei cel mai simplu cod posibil — bubble sort, dar doar pentru valori mici.
• Date multe, performanță reală — quicksort sau mergesort.
• Ai nevoie de stabilitate (păstrarea ordinii elementelor egale) — mergesort.

std::sort: ce folosești în viața reală

Vestea bună: în practică nu îți scrii singur algoritmul de sortare. C++ îți oferă std::sort din biblioteca <algorithm>, optimizat și rapid (folosește o combinație de quicksort, heapsort și insertion sort).

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {5, 2, 9, 1, 7};

    // sortare crescătoare
    sort(v.begin(), v.end());
    for (int x : v) cout << x << " ";
    cout << "\n";

    // sortare descrescătoare cu o funcție de comparare
    sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;
    });
    for (int x : v) cout << x << " ";
    return 0;
}

Acel [](int a, int b) { return a > b; } se numește funcție lambda și îi spune lui sort ce înseamnă "ordinea corectă". Returnezi true când a trebuie să stea înaintea lui b. Așa poți sorta după orice criteriu: descrescător, după a doua cifră, după lungimea unui cuvânt sau după mai multe câmpuri ale unei structuri.

std::sort rulează în O(n log n) și e aproape mereu alegerea corectă în cod real. Algoritmii pe care i-am scris manual rămân importanți însă pentru examen: ei îți arată că înțelegi cum se sortează, nu doar că apeși un buton.

Concluzie

Acum ai harta completă: bubble, selection și insertion ca să prinzi mecanica, quicksort și mergesort pentru viteză, iar std::sort pentru cod real. Secretul nu e să-i memorezi, ci să înțelegi de ce unul face O(n²) operații, iar altul O(n log n) — acolo se câștigă punctele la Bac.

La ByteSchool exersezi exact astfel de algoritmi pe probleme reale, alături de mentori care lucrează în companii mari din tech. Te ajutăm să treci de la "îmi amintesc codul" la "înțeleg de ce funcționează" — diferența care contează în ziua examenului și mai apoi în orice job din programare.