Sortarea unui vector

Una dintre cele mai frecvente operații cu vectori este sortarea - aranjarea elementelor într-o anumită ordine (crescătoare sau descrescătoare).

Exemple:

• 3 7 2 9 4 sortat crescător: 2 3 4 7 9
• 3 7 2 9 4 sortat descrescător: 9 7 4 3 2

De ce avem nevoie de sortare?

• pentru a afișa un clasament (de la cel mai mare la cel mai mic);
• pentru a găsi mai ușor o valoare (căutarea binară funcționează doar pe vectori sortați);
• pentru a elimina duplicate mai eficient;
• pentru a rezolva multe probleme de concurs.

Metoda 1: Sortarea prin selecție (Selection Sort)

Ideea

La fiecare pas, căutăm cel mai mic element din partea nesortată și îl punem pe poziția corectă.

Algoritmul

1. Parcurgem vectorul de la poziția 1 la n.
2. Pentru fiecare poziție i, căutăm minimul din v[i], v[i+1], ..., v[n].
3. Interschimbăm minimul găsit cu v[i].
4. Acum v[i] conține valoarea corectă, trecem la i + 1.

Codul

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    for (int i = 1; i < n; i++) {
        int pozMin = i;

        for (int j = i + 1; j <= n; j++) {
            if (v[j] < v[pozMin]) {
                pozMin = j;
            }
        }

        // Interschimbăm v[i] cu v[pozMin]
        int aux = v[i];
        v[i] = v[pozMin];
        v[pozMin] = aux;
    }

    for (int i = 1; i <= n; i++) {
        fout << v[i] << " ";
    }

    return 0;
}

date.in:

5
3 7 2 9 4

date.out:

2 3 4 7 9

Pas cu pas

Vector inițial: 3 7 2 9 4

Metoda 2: Sortarea prin metoda bulelor (Bubble Sort)

Ideea

Comparăm elemente vecine și le interschimbăm dacă sunt în ordine greșită. Repetăm până când vectorul este sortat.

La fiecare parcurgere, cel mai mare element „urcă” spre final, ca un balon (de aici numele).

Algoritmul

1. Parcurgem vectorul și comparăm v[i] cu v[i+1].
2. Dacă v[i] > v[i+1], le interschimbăm.
3. Repetăm parcurgerea până când nu mai facem nicio interschimbare.

Codul

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int sortat = 0;

    while (sortat == 0) {
        sortat = 1;

        for (int i = 1; i < n; i++) {
            if (v[i] > v[i + 1]) {
                int aux = v[i];
                v[i] = v[i + 1];
                v[i + 1] = aux;
                sortat = 0;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        fout << v[i] << " ";
    }

    return 0;
}

date.in:

5
3 7 2 9 4

date.out:

2 3 4 7 9

Pas cu pas

Vector inițial: 3 7 2 9 4

Parcurgerea 1:

Am făcut interschimbări → continuăm.

Parcurgerea 2:

Am făcut interschimbări → continuăm.

Parcurgerea 3:

Nicio interschimbare → vectorul este sortat!

Sortare descrescătoare

Pentru a sorta descrescător, inversăm condiția de comparare:

Selection Sort descrescător: căutăm maximul în loc de minim:

if (v[j] > v[pozMax]) {
    pozMax = j;
}

Bubble Sort descrescător: interschimbăm când v[i] < v[i+1]:

if (v[i] < v[i + 1]) {
    // interschimbăm
}

Comparație între metode

Interschimbarea - operația de bază

Interschimbarea apare în orice algoritm de sortare. Forma standard:

int aux = v[i];
v[i] = v[j];
v[j] = aux;

De ce avem nevoie de aux?

Fără variabila auxiliară:

v[i] = v[j]; // am pierdut valoarea veche a lui v[i]!
v[j] = v[i]; // acum ambele au valoarea lui v[j]

Cu aux, salvăm mai întâi valoarea veche:

aux = v[i];   // salvăm v[i]
v[i] = v[j];  // v[i] primește valoarea lui v[j]
v[j] = aux;   // v[j] primește valoarea veche a lui v[i]

Exemplu complet: sortare și afișare mediană

Mediana este elementul din mijlocul vectorului sortat.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    // Sortăm crescător (Selection Sort)
    for (int i = 1; i < n; i++) {
        int pozMin = i;
        for (int j = i + 1; j <= n; j++) {
            if (v[j] < v[pozMin]) {
                pozMin = j;
            }
        }
        int aux = v[i];
        v[i] = v[pozMin];
        v[pozMin] = aux;
    }

    // Mediana
    fout << v[(n + 1) / 2];

    return 0;
}

date.in:

5
3 7 2 9 4

date.out:

4

Vectorul sortat: 2 3 4 7 9. Elementul din mijloc (poziția 3): 4.

Greșeli frecvente

1. Interschimbarea fără variabilă auxiliară

// GREȘIT:
v[i] = v[j];
v[j] = v[i]; // ambele au acum aceeași valoare!

Folosește mereu aux.

2. Bucla exterioară merge până la n în loc de n - 1

La Selection Sort:

for (int i = 1; i < n; i++) { // < n, NU <= n

Ultimul element rămâne automat pe loc - nu trebuie procesat.

3. Bubble Sort fără condiție de oprire

// GREȘIT: face mereu n parcurgeri, chiar dacă e deja sortat
for (int pas = 1; pas < n; pas++) {
    for (int i = 1; i < n; i++) {
        // ...
    }
}

Varianta cu sortat (flag) se oprește imediat ce nu mai sunt interschimbări.

4. Confuzia între sortare crescătoare și descrescătoare

• Crescător: v[i] > v[i+1] → interschimbăm (mutăm pe cel mare la dreapta)
• Descrescător: v[i] < v[i+1] → interschimbăm (mutăm pe cel mic la dreapta)

Ce să reții

• Selection Sort: la fiecare pas, selectăm minimul din partea nesortată și îl punem pe loc.
• Bubble Sort: comparăm vecini și îi interschimbăm; repetăm până e sortat.
• Interschimbarea necesită variabilă auxiliară (aux).
• Pentru sortare descrescătoare, inversăm condiția de comparare.
• Ambele metode sunt bune pentru vectori mici (sub câteva mii de elemente).
• La concursuri de clasa a V-a, oricare dintre cele două este acceptată.

Probleme

pbinfoOrdonare→

pbinfoSortprime→

pbinfoKsort→

pbinfoSortmax→

pbinfoPuzzle1→