Inversarea vectorilor

De ce contează?

Ai un rând de elevi și vrei să-i pui în ordine inversă. Cea mai eficientă metodă: primul și ultimul fac schimb de locuri, apoi al doilea cu penultimul, și tot așa spre mijloc. Când ajungi la centru, gata — fără să muți pe nimeni de două ori.

Ideea: doi indici care se apropie

Inversarea „pe loc" folosește doi indici: st (start) de la 0 și dr (sfârșit) de la n−1. Schimbi v[st] cu v[dr], apoi îi apropii. Te oprești când se întâlnesc.

v	5	3	8	1	9	2
	0	1	2	3	4	5
	st					dr

Primul pas: schimbi v[st]=5 cu v[dr]=2. Apoi st crește, dr scade, și repeți spre mijloc.

Algoritm pas cu pas:

st	dr	schimbăm	vector
0	5	5 ↔ 2	2 3 8 1 9 5
1	4	3 ↔ 9	2 9 8 1 3 5
2	3	8 ↔ 1	2 9 1 8 3 5
3	2	st ≥ dr → stop	(inversat)

După 3 schimburi (n/2), vectorul e complet inversat: 2 9 1 8 3 5.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int v[1000];
    for (int i = 0; i < n; i++) cin >> v[i];

    int st = 0, dr = n - 1;
    while (st < dr) {
        swap(v[st], v[dr]);     // schimbam capetele
        st++;                   // ne apropiem de mijloc
        dr--;
    }

    for (int i = 0; i < n; i++) cout << v[i] << " ";
    return 0;
}

Observația-cheie

Condiția st < dr e cheia. Faci exact n/2 schimburi. Dacă ai merge până st < n, ai schimba fiecare pereche de două ori — a doua oară anulează prima și vectorul revine neschimbat.

Alternativă: într-un vector nou

Dacă ai voie cu memorie suplimentară, copiezi de la coadă la cap:

for (int i = 0; i < n; i++) {
    rezultat[i] = v[n - 1 - i];     // v[n-1], v[n-2], ...
}

Mai simplu de citit, dar folosește O(n) memorie în plus. Varianta „pe loc" e preferată.

Complexitate

Variantă	Timp	Spațiu
pe loc (doi indici)	O(n)	O(1)
vector nou	O(n)	O(n)

Greșeli frecvente

Capcane reale la inversare:

Bucla până la n: inversezi fiecare pereche de două ori → vectorul rămâne la fel. Oprește-te la mijloc (st < dr).
Indice greșit la copiere: v[n - i] în loc de v[n - 1 - i] iese din vector la i = 0.
Uiți să apropii ambii indici: crești doar st (sau scazi doar dr) → buclă infinită sau inversare incompletă.
Confuzi inversarea cu sortarea descrescătoare: inversarea doar oglindește ordinea existentă, nu o ordonează.

De reținut

Inversare pe loc = doi indici (st, dr) care fac swap și se apropie spre mijloc.
Bucla merge până st < dr → exact n/2 schimburi; nu inversa de două ori.
O(n) timp, O(1) memorie; copierea într-un vector nou costă O(n) memorie în plus.