Sortări pătratice

De ce contează?

Aranjezi cărți de joc în mână. O metodă: cauți cea mai mică și o pui prima, apoi cea mai mică dintre rămase, și tot așa (selecție). Alta: iei cărțile pe rând și o strecori pe fiecare la locul ei printre cele deja aranjate (inserție). Ambele sortează — diferă cum.

Ce înseamnă „sortare pătratică"

Sortările pătratice ordonează vectorul cu două bucle imbricate → ~n² operații, deci O(n²). Sunt simple și bune de înțeles, dar lente pentru n mare. Vedem două: selecția și inserția.

Sortarea prin selecție

La fiecare pas, găsești minimul din partea nesortată și îl aduci la începutul ei:

Pas	vector	minim adus
0	5 3 8 1 9	1 → 1 3 8 5 9
1	1 3 8 5 9	3 (deja)
2	1 3 8 5 9	5 → 1 3 5 8 9
3	1 3 5 8 9	8 (deja)

#include <iostream>
using namespace std;

void selectie(int v[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int pozMin = i;                     // presupunem minimul aici
        for (int j = i + 1; j < n; j++) {
            if (v[j] < v[pozMin]) pozMin = j;
        }
        swap(v[i], v[pozMin]);              // aducem minimul pe pozitia i
    }
}

int main() {
    int v[] = {5, 3, 8, 1, 9};
    selectie(v, 5);
    for (int i = 0; i < 5; i++) cout << v[i] << " ";   // 1 3 5 8 9
    return 0;
}

Sortarea prin inserție

Iei fiecare element și îl „strecori" la locul lui printre cele deja sortate din stânga:

void insertie(int v[], int n) {
    for (int i = 1; i < n; i++) {
        int val = v[i];                     // elementul de inserat
        int j = i - 1;
        while (j >= 0 && v[j] > val) {       // mutam la dreapta cat e nevoie
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = val;                      // il punem la locul gasit
    }
}

După sortare, vectorul e ordonat crescător. Selecția și inserția dau același rezultat, pe drumuri diferite.

Observația-cheie

Inserția are un mare avantaj: pe un vector aproape sortat, fiecare element se mișcă foarte puțin, deci se apropie de O(n). Selecția face mereu același număr de comparații, O(n²), indiferent de date.

Complexitate

Sortare	Cel mai bun	Mediu / rău	Spațiu
selecție	O(n²)	O(n²)	O(1)
inserție	O(n) (aproape sortat)	O(n²)	O(1)

Pentru n mare (peste ~10⁴–10⁵), folosește std::sort (O(n log n)). Sortările pătratice sunt pentru n mic sau pentru a înțelege mecanica.

Vizualizare

Urmărește cum se construiește partea sortată pas cu pas și cum se aleg/mută elementele:

Indiciu

Pornește vizualizarea cu un vector mic și observă cum, la selecție, zona sortată din stânga crește cu un element la fiecare trecere completă prin restul vectorului.

Greșeli frecvente

Capcane reale la sortările pătratice:

O(n²) pe n mare: corect, dar depășește timpul peste ~10⁵ elemente. Folosește std::sort.
Indici greșiți la inserție: v[j + 1] = v[j] cu j ajuns sub 0 → acces în afara vectorului. Condiția j >= 0 în while te protejează.
Selecție fără pozMin: faci swap direct la fiecare comparație în loc să reții poziția minimului — multe schimburi inutile.
Uiți cazul deja sortat: la inserție, while nu rulează dacă elementul e la locul lui — corect și eficient; nu adăuga schimburi forțate.

De reținut

Pătratice = două bucle imbricate, O(n²); selecția aduce minimul, inserția strecoară elementul.
Inserția se apropie de O(n) pe vectori aproape sortați; selecția e mereu O(n²).
Pentru n mare, treci la std::sort (O(n log n)).