`std::stable_sort` în C++

Sortează un interval păstrând ordinea inițială a elementelor considerate egale.

Sintaxă

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

Ce face `std::stable_sort`

std::stable_sort sortează ca std::sort, dar garantează că elementele egale (după criteriul de comparare) rămân în ordinea în care erau înainte. Se numește sortare stabilă.

Este util când sortezi după mai multe criterii pe rând: sortezi întâi după nume, apoi stabil după oraș, și persoanele din același oraș rămân în ordine alfabetică. Poate folosi memorie suplimentară și este de obicei puțin mai lentă decât std::sort.

Parametri

Parametru	Descriere
`first, last`	Intervalul de sortat.
`comp`	Opțional. Funcția de comparare, ca la `std::sort`.

Ce returnează

Nimic.

Exemple

Exemplul 1: Comenzi sortate după oraș, în ordinea sosirii

Comenzile din același oraș își păstrează ordinea inițială (numărul comenzii crește).

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

struct Comanda {
    int numar;
    std::string oras;
};

int main() {
    std::vector<Comanda> comenzi{
        {101, "Iași"}, {102, "Cluj"}, {103, "Iași"}, {104, "Brașov"}, {105, "Cluj"}, {106, "Iași"}};

    std::stable_sort(comenzi.begin(), comenzi.end(),
                     [](const Comanda& a, const Comanda& b) { return a.oras < b.oras; });

    for (const Comanda& c : comenzi) {
        std::println("{} {}", c.oras, c.numar);
    }
}

Rezultat

Brașov 104
Cluj 102
Cluj 105
Iași 101
Iași 103
Iași 106

Exemplul 2: Sortare după lungime, cu ranges

std::ranges::stable_sort primește o proiecție: aici fiecare cuvânt este comparat după size(). Cuvintele de aceeași lungime rămân în ordinea din vector.

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

int main() {
    std::vector<std::string> cuvinte{"mere", "kiwi", "pere", "banane", "nuci", "caise"};

    std::ranges::stable_sort(cuvinte, {}, &std::string::size);
    std::println("{}", cuvinte);
}