Funcția sort din STL – Cum să sortezi vectorii simplu în C++!

În programare, tot timpul avem de sortat vectori, și este destul de enervant să scriem de fiecare dată un algoritm de sortare pentru asta, mai ales dacă dorim unul eficient, pentru că trebuie să-l regândim și să fim foarte atenți la implementare. C++, la fel ca orice limbaj de programare care se respectă, oferă o funcție pentru sortare, numită sort. În acest articol voi prezenta cum se folosește funcția sort și de ce ne ușurează munca. Nu este nevoie să știți prea multe despre funcții, sau alte teme mai avansate (față de clasa a 9-a).

Structura funcției sort

Funcția sort este definită în biblioteca algorithm, deci pentru a o putea folosi, trebuie să scriem pe la începutul programului #include <algorithm>. Prima formă a funcției sort este următoarea:

void sort(RandomAccessIterator first, RandomAccessIterator last);

Keyword-ul void indică faptul că funcția nu returnează nimic; ea doar efectuează o sortare pe vectorul dat. Cei doi parametri, ce se scriu între paranteze, reprezintă doi pointeri: first și last. Secvența de elemente ce va fi sortată începe pe poziția first și se termină pe last - 1. Cu alte cuvinte, se vor sorta elementele din intervalul [first, last).

Pentru a înțelege mai bine, să luăm un exemplu. Avem vectorul static v cu n = 7 elemente, declarat și inițializat ca mai jos:

int v[] = {3, 7, 2, 9, 0, 1, 8};

Un pointer reprezintă adresa de memorie unde este stocată o variabilă. Pentru a ne referi la un pointer către elementul aflat pe prima poziție (poziția 0) din vectorul v, vom scrie pur și simplu v. Pentru a indica al doilea element (de pe poziția 1), vom scrie v + 1. În general, v + i este pointer-ul către poziția cu numărul i din v. Așadar, iată cum se poate apela funcția sort pentru a sorta vectorul v:

sort(v, v + n);

Da, v + n practic nu indică o poziție din vector, ci de fapt prima zonă de memorie de tipul lui v (int) de după ultimul element.

Dacă v era indexat de la 1, am fi scris:

sort(v + 1, v + n + 1);

Iată cât de simplu este să sortăm un vector folosind funcția sort. Trebuie doar să specificăm începutul și sfârșitul lui. Mai jos este un program complet care citește de la tastatură un vector v, cu n elemente, și îl afișează sortat:

#include <iostream>
#include <algorithm>

int n;
int v[618];

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

    sort(v, v + n);
    for (int i = 0; i < n; i++)
        cout << v[i] << ' ';
    cout << '\n';
    return 0;
}

Sortarea unei anumite secvențe din vector

De acum ne vom juca cu funcția sort pentru a efectua și sortări mai puțin obișnuite. De exemplu, vrem să sortăm doar elementele cuprinse între pozițiile a și b (inclusiv). Ei bine, din ce am explicat mai sus legat de pointeri, soluția este:

sort(v + a, v + b + 1);

De exemplu:

int v[] = {4, 6, 2, 3, 9, 3};
cin >> a >> b; // Se introduce: 1 3

sort(v + a, v + b + 1);
for (int i = 0; i < 5; i++)
    cout << v[i] << ' ';
cout << '\n'; // Se afișează: 4 2 3 6 9 3

Sortarea descrescătoare a vectorului

Până acum am sortat crescător vectorul, dar cum facem să-l sortăm descrescător, folosind în continuare sort? Ei bine, aici intervine a doua variantă a funcției:

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

După apelul acestei funcții, vectorul dat va fi sortat după criteriul comp, unde comp este un pointer către o funcție (nu are legătură cu pointerii de mai sus; este pur și simplu numele funcției) declarată ca mai jos:

bool cmp(int a, int b);

Pe această funcție o vom defini noi. Trebuie să returneze true dacă vrem ca a să apară înaintea lui b în vectorul sortat, sau false în caz contrar. Altfel spus, funcția asta trebuie să facă echivalentul operatorului < din sortarea obișnuită.

Deci, pentru a sorta vectorul v descrescător, funcția comp va arăta așa:

bool cmp(int a, int b) {
    return a > b;
}

Iar sort-ul va fi apelat astfel:

sort(v, v + n, cmp);

Atenție! Funcția cmp trebuie să implementeze echivalentul operatorului <, nu <=.

Evident, dacă vectorul v este de alt tip decât int, atunci parametrii funcției cmp (care, apropo, poate avea orice nume) trebuie să fie de acel tip. De exemplu, dacă lucrăm cu un vector de tip double, funcția cmp va fi declarată așa:

bool cmp(double a, double b);

Sortarea vectorilor de structuri

Un alt avantaj major al funcției sort este că dacă vrem să sortăm un vector cu elemente de tip struct, trebuie doar să definim criteriul de comparare. De restul se ocupă sort

De exemplu, avem un vector cu elemente de tip Product:

struct Product {   // informații despre un produs
    float price;   // preț
    int quantity;  // cantitatea disponibilă
    char name[50]; // nume (ca șir de caractere)
};

Vrem ca în vectorul v produsele să fie ordonate crescător după preț. În caz de egalitate la preț, descrescător după cantitate. În caz de egalitate și la cantitate, crescător după nume.

Pentru cine nu știe, câmpul name este un șir de caractere, iar pentru a testa dacă șirul a este mai mic lexicografic (alfabetic) decât șirul b, facem testul următor:

strcmp(a, b) < 0 // #include <cstring> pentru strcmp

Deci, funcția de comparare va arăta așa:

bool cmp(Product a, Product b) {
    return (a.price < b.price)
        || (a.price == b.price && a.quantity > b.quantity)
        || (a.price == b.price && a.quantity == b.quantiy && strcmp(a, b) < 0);
}

Supraîncărcarea operatorului <

Apelul funcției sort (în prima formă) funcționează doar dacă pentru tipul de date respectiv operatorul < este definit. Pentru un struct creat de noi, putem apela sort folosind o funcție cmp, cum am făcut mai sus; însă, soluția pe care o prefer (pentru că e mai elegantă) este să supraîncarc (să definesc) operatorul < pentru acel struct, ca apoi să apelez funcția sort în forma ei simplă. Iată cum se supraîncarcă operatorul <:

bool operator<(NumeStruct a, NumeStruct b) {
    // Aici scriem ce scriam și în funcția cmp, adică ce
    // vrem să facă operatorul < pentru acest tip de date.
}

De exemplu, în cazul de mai sus, cu produsele, operatorul < va arăta așa:

bool operator<(Product a, Product b) {
    return (a.price < b.price)
        || (a.price == b.price && a.quantity > b.quantity)
        || (a.price == b.price && a.quantity == b.quantiy && strcmp(a, b)) < 0;
}

Astfel, pentru a sorta un vector v de tip Product, va fi de ajuns să scriem sort(v, v + n).

Totuși, nu este mereu OK să facem asta. De exemplu, într-o problemă s-ar putea să avem nevoie de două criterii de sortare pentru același tip de date, caz în care este mai bine să definim două funcții de comparare, cmp1 și cmp2. În plus, pentru tipuri de date standard, ca int, ar fi un dezastru să supraîncărcăm operatori. În cazul lor, soluția este să scriem o funcție cmp, cum am făcut pentru sortarea descrescătoare.

Funcția sort pe vectori din STL

Desigur, fiind o funcție din STL (Standard Template Library), sort funcționează și pe containere STL, precum vector și string:

vector<int> v = {6, 1, 8};
sort(v.begin(), v.end());

string str = "InfoGenius.ro";
sort(str.begin(), str.end());

Concluzie

Funcția sort ne face viața mult mai ușoară, și poate fi folosită fără să știm algoritmi de sortare în $O(n \log n)$ Apropo, sort-ul din STL este o combinație isteață între QuickSort randomizat și HeapSort, numită IntroSort. Ar fi îngrozitor să implementăm noi acest algoritm. Funcția sort este cel mai bun mod de a sorta un vector în C++, mai puțin atunci când putem realiza o sortare prin numărare.

Aici găsiți documentația oficială. Dacă aveți vreo întrebare despre funcția sort din STL, nu ezitați să o adresați mai jos, în secțiunea de comentarii