std::sort în C++

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

Ce face std::sort

std::sort ordonează elementele dintre doi iteratori, de obicei v.begin() și v.end(). Implicit folosește operatorul <, deci rezultatul este crescător. Complexitatea este O(n log n).

Pentru altă ordine dai un al treilea argument, o funcție de comparare care spune dacă primul element trebuie pus înaintea celui de-al doilea: std::greater<>() pentru descrescător sau o funcție lambda.

Din C++20 poți scrie mai scurt std::ranges::sort(v), fără begin() și end(). std::sort nu păstrează ordinea elementelor egale; dacă ai nevoie de asta, folosește std::stable_sort.

Parametri

Parametru	Descriere
first, last	Intervalul de sortat: [first, last). Iteratorii trebuie să permită acces direct (vector, array, deque, șir C), deci nu merge pe std::list.
comp	Opțional. Funcție bool(a, b) care returnează true dacă a trebuie să stea înaintea lui b.

Ce returnează

Nimic. Elementele sunt rearanjate în containerul original.

Exemple

Exemplul 1: Crescător și descrescător

std::greater<>() inversează ordinea. Varianta cu std::ranges::sort face același lucru, cu mai puțin de scris.

#include <algorithm>
#include <functional>
#include <print>
#include <vector>

int main() {
    std::vector<int> note{7, 10, 5, 9, 8};

    std::sort(note.begin(), note.end());
    std::println("Crescător:    {}", note);

    std::sort(note.begin(), note.end(), std::greater<>());
    std::println("Descrescător: {}", note);

    std::ranges::sort(note);  // C++20, același lucru ca primul sort
    std::println("Ranges:       {}", note);
}

Rezultat

Crescător:    [5, 7, 8, 9, 10]
Descrescător: [10, 9, 8, 7, 5]
Ranges:       [5, 7, 8, 9, 10]

Exemplul 2: Sortarea unor structuri după un câmp

Funcția lambda compară doi elevi după medie, descrescător. Dacă mediile sunt egale, îi ordonează după nume.

#include <algorithm>
#include <print>
#include <string>
#include <vector>

struct Elev {
    std::string nume;
    double medie;
};

int main() {
    std::vector<Elev> clasa{{"Ion", 8.50}, {"Ana", 9.75}, {"Maria", 8.50}, {"Radu", 7.20}};

    std::sort(clasa.begin(), clasa.end(), [](const Elev& a, const Elev& b) {
        if (a.medie != b.medie) {
            return a.medie > b.medie;
        }
        return a.nume < b.nume;
    });

    for (const Elev& e : clasa) {
        std::println("{:<6} {:.2f}", e.nume, e.medie);
    }
}

Rezultat

Ana    9.75
Ion    8.50
Maria  8.50
Radu   7.20

Exemplul 3: Sortarea unui șir C și a unui text

Merge și pe tablouri clasice (pointerii sunt iteratori) și pe std::string, unde sortează literele.

#include <algorithm>
#include <iterator>
#include <print>
#include <string>

int main() {
    int preturi[] = {45, 12, 99, 30};
    std::sort(std::begin(preturi), std::end(preturi));
    for (int p : preturi) {
        std::print("{} ", p);
    }
    std::println("");

    std::string cuvant = "programare";
    std::sort(cuvant.begin(), cuvant.end());
    std::println("{}", cuvant);
}

Rezultat

12 30 45 99 
aaegmoprrr

Greșeli frecvente

• Funcția de comparare folosește <= în loc de <. Comparatorul trebuie să returneze false pentru elemente egale; altfel comportamentul este nedefinit și programul poate chiar citi în afara vectorului.
• Încerci std::sort(lista.begin(), lista.end()) pe o std::list: nu compilează, pentru că lista nu are iteratori cu acces direct. Folosește lista.sort().
• Sortezi texte cu diacritice și te miri că „Ștefan” apare după „Zoe”. Compararea se face pe octeți, nu după alfabetul românesc.

Comenzi înrudite

• std::stable_sort: Sortează un interval păstrând ordinea inițială a elementelor considerate egale.
• std::ranges::sort: Sortează un container întreg dintr-un apel, cu opțiunea de a sorta după un câmp (proiecție).
• std::partial_sort: Pune în ordine doar primele k elemente (cele mai mici sau cele mai mari), restul rămân neordonate.
• std::nth_element: Pune pe poziția n elementul care ar fi acolo după sortare; util pentru mediană sau al k-lea cel mai mic.
• std::is_sorted: Verifică dacă elementele unui interval sunt deja în ordine crescătoare (sau după regula dată).
• std::binary_search: Verifică foarte rapid dacă o valoare există într-un interval deja sortat.