Inversarea unui vector

De ce contează?

Ai o linie de 6 elevi ordonați după înălțime, de la cel mai scund la cel mai înalt. Vrei să inversezi ordinea — nu să-i muți pe toți, ci să schimbi cel mai scund cu cel mai înalt, al doilea cu penultimul, și tot așa. Trei schimburi și gata.

Algoritmul de inversare

Menținem doi indici: st (stânga, pornind de la 0) și dr (dreapta, pornind de la n-1). La fiecare pas îi apropiem cu câte un pas spre centru:

st ← 0, dr ← n-1
cat timp st < dr:
    swap(v[st], v[dr])
    st ← st + 1
    dr ← dr - 1

Urmărire pe v = {1, 2, 3, 4, 5}:

Pas 1: swap(v[0], v[4]) → {5, 2, 3, 4, 1}   st=1, dr=3
Pas 2: swap(v[1], v[3]) → {5, 4, 3, 2, 1}   st=2, dr=2
st = dr → stop (elementul din mijloc rămâne pe loc)
Rezultat: {5, 4, 3, 2, 1}

Implementare C++

#include <iostream>
using namespace std;

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

    int st = 0, dr = n - 1;
    while (st < dr) {
        int t = v[st];    // salveaza temporar
        v[st] = v[dr];
        v[dr] = t;
        st++;
        dr--;
    }

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

Alternativ, cu swap din STL (include <algorithm>):

while (st < dr) {
    swap(v[st], v[dr]);
    st++; dr--;
}

Varianta cu copie

int w[1001];
for (int i = 0; i < n; i++) w[i] = v[n - 1 - i];
// w e inversul lui v

Folosește O(n) spațiu suplimentar — corectă, dar varianta cu swap e preferabilă când nu ai nevoie să păstrezi originalul.

Complexitate

Variantă	Timp	Spațiu
Swap pe loc	O(n)	O(1)
Cu copie	O(n)	O(n)

Observația-cheie

Swap-ul clasic necesită variabilă temporară t. C++ oferă std::swap(a, b) care face exact asta intern — poți folosi direct fără să-ți mai declari t.

Vizualizare

Urmărește cum cei doi indici st și dr se apropie spre centru, interschimbând elementele la fiecare pas:

Greșeli frecvente

Greșeala 1: v[st] = v[dr]; v[dr] = v[st]; fără variabilă temporară — prima valoare se pierde înainte de a fi salvată.

Greșeala 2: Bucla for (int i = 0; i < n; i++) face n swap-uri — vectorul se inversează și se re-inversează, revenind la original. Inversarea e completă după exact n/2 swap-uri.

Greșeala 3: Condiția st <= dr face un swap inutil când n e impar și st == dr — elementul din mijloc se interschimbă cu el însuși. Folosește st < dr.

Recapitulare

Inversarea folosește doi indici (st, dr) care se apropie spre mijloc.
La fiecare pas: swap(v[st], v[dr]), st++, dr--.
Complexitate O(n), fără memorie suplimentară.