Sortarea vectorilor: selecție și std::sort în C++

Sortarea rearanjează elementele într-o ordine stabilită, de exemplu crescător. Valorile nu dispar și nu se adaugă: se schimbă pozițiile lor. Vectorul 5 2 4 1 devine 1 2 4 5, iar 3 1 3 devine 1 3 3.

Lecția presupune că poți parcurge un vector și găsi un minim. Vom urmări o metodă simplă pentru înțelegere, apoi operația standard folosită în multe soluții C++.

Sortarea prin selecție

La pasul i, căutăm cel mai mic element din porțiunea care începe la i. Îl aducem pe poziția i, printr-un schimb. Astfel, partea din stânga crește cu un element aflat deja pe poziția sa finală.

Programul citește n, cu 0 <= n <= 1000, și n numere întregi între -1000000000 și 1000000000, apoi le afișează crescător.

Varianta cu tablou clasic

Tabloul a[1000] are capacitate fixă. Datele ocupă doar primele n poziții, iar indicii folosiți sunt de la 0 la n - 1. Limita lui n trebuie să respecte această capacitate.

#include <iostream>
#include <utility>

int main() {
    int n = 0;
    std::cin >> n;
    int a[1000]{};
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i + 1 < n; ++i) {
        int pozMinim = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[pozMinim]) {
                pozMinim = j;
            }
        }
        std::swap(a[i], a[pozMinim]);
    }
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            std::cout << ' ';
        }
        std::cout << a[i];
    }
    std::cout << '\n';
    return 0;
}

Varianta cu std::vector

std::vector<int> a(n) creează exact n elemente. Citirea, accesul a[i] și algoritmul rămân aceleași; se schimbă declararea și modul de gestionare a dimensiunii.

#include <iostream>
#include <vector>
#include <utility>

int main() {
    int n = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i + 1 < n; ++i) {
        int pozMinim = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[pozMinim]) {
                pozMinim = j;
            }
        }
        std::swap(a[i], a[pozMinim]);
    }
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            std::cout << ' ';
        }
        std::cout << a[i];
    }
    std::cout << '\n';
    return 0;
}

pozMinim este un indice, nu valoarea minimă. Îl resetăm la i la începutul fiecărui pas. std::swap, disponibil prin <utility>, schimbă cele două valori fără să o piardă pe vreuna dintre ele.

Selecția minimului: comparăm întâi, apoi facem un singur schimb pentru poziția i.Redă animațiaO singură rulare · 23 secunde

Pentru 5 2 4 1, primul pas găsește minimul 1 la indicele 3 și îl schimbă cu 5. Vectorul devine 1 2 4 5. Următorii pași confirmă că 2 și 4 sunt deja cele mai mici valori din porțiunile rămase. Un schimb al unui element cu el însuși nu modifică vectorul.

De ce funcționează

Înaintea pasului i, primele i elemente sunt cele mai mici valori, deja ordonate. Căutarea examinează întreaga parte rămasă, deci valoarea aleasă este exact următoarea care trebuie așezată. După schimb, proprietatea rămâne adevărată pentru primele i + 1 elemente.

Când rămâne un singur element, nu mai trebuie să îl cauți: celelalte sunt deja plasate. Pentru n = 0 sau n = 1, bucla de sortare nu se execută. Valorile repetate sunt păstrate; algoritmul nu elimină duplicatele.

std::sort pentru soluțiile uzuale

Biblioteca standard oferă std::sort, declarată în <algorithm>. Următorul program acceptă 0 <= n <= 100000, cu aceleași limite pentru valori.

Varianta cu tablou clasic

Tabloul a[100000] are capacitate fixă. Datele ocupă doar primele n poziții, iar indicii folosiți sunt de la 0 la n - 1. Limita lui n trebuie să respecte această capacitate.

#include <algorithm>
#include <iostream>

int main() {
    int n = 0;
    std::cin >> n;
    int a[100000]{};
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::sort(a, a + n);
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            std::cout << ' ';
        }
        std::cout << a[i];
    }
    std::cout << '\n';
    return 0;
}

Varianta cu std::vector

std::vector<int> a(n) creează exact n elemente. Citirea, accesul a[i] și algoritmul rămân aceleași; se schimbă declararea și modul de gestionare a dimensiunii. Pentru sortare, capetele a și a + n devin a.begin() și a.end().

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    int n = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            std::cout << ' ';
        }
        std::cout << a[i];
    }
    std::cout << '\n';
    return 0;
}

begin() indică începutul, iar end() poziția de după ultimul element. Intervalul de sortat include începutul și exclude sfârșitul. Nu accesa elementul de la end(). Pentru un vector gol, cele două capete coincid și sortarea nu are nimic de făcut.

Cost și efecte asupra datelor

Selecția face (n - 1) + (n - 2) + ... + 1 comparații, deci are timp O(n²), chiar dacă datele sunt deja ordonate. Folosește O(1) memorie suplimentară față de vector. std::sort are O(n log n) comparații pentru n > 1, motiv pentru care este preferabil pentru volume mai mari.

După sortare, indicii nu mai descriu pozițiile originale. Dacă enunțul cere acele poziții, trebuie să le păstrezi împreună cu valorile. Nici selecția prezentată, nici std::sort nu garantează păstrarea ordinii relative a elementelor egale care ar avea și alte informații asociate.

În variantele clasice, memoria rezervată este dată de capacitatea din declarație, nu de numărul de elemente folosite. În variantele cu std::vector, stocarea din aceste exemple este proporțională cu dimensiunile citite. Algoritmul și numărul de elemente prelucrate nu se schimbă între reprezentări. Inițializarea cu {} a tabloului clasic pune la zero întreaga capacitate, inclusiv pozițiile nefolosite; acest cost este separat de parcurgerea celor n elemente sau a celor n * m celule.

Exersează

1. Ce rezultat obții pentru 4 -1 4 0?
2. Ce se întâmplă dacă nu resetezi pozMinim la fiecare pas?
3. Câte comparații face selecția pentru patru elemente?
4. Sortarea elimină valorile repetate?

Răspunsuri: -1 0 4 4; poți alege un indice din partea deja prelucrată și strica rezultatul; 3 + 2 + 1 = 6; nu. Pentru eliminarea duplicatelor este nevoie de o prelucrare separată.

Continuă cu secvențe și prelucrări.