`std::partial_sort` în C++

Pune în ordine doar primele k elemente (cele mai mici sau cele mai mari), restul rămân neordonate.

Sintaxă

void partial_sort(RandomIt first, RandomIt middle, RandomIt last);
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);

Ce face `std::partial_sort`

std::partial_sort aduce la începutul intervalului cele mai mici middle - first elemente, în ordine crescătoare. Elementele de după middle rămân într-o ordine nespecificată.

Este mai rapid decât o sortare completă când ai nevoie doar de un „top”: primele 3 note, cele mai ieftine 10 produse.

Parametri

Parametru	Descriere
`first, last`	Intervalul complet.
`middle`	Unde se termină partea sortată. Primele `middle - first` poziții primesc elementele cele mai mici, în ordine.
`comp`	Opțional. Funcția de comparare; cu `std::greater<>()` obții cele mai mari elemente.

Ce returnează

Nimic.

Exemple

Exemplul 1: Top 3 punctaje

Afișăm doar primele 3 poziții, singurele garantate ca ordine.

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

int main() {
    std::vector<int> punctaje{56, 91, 73, 88, 45, 97, 60};

    std::partial_sort(punctaje.begin(), punctaje.begin() + 3, punctaje.end(), std::greater<>());

    std::println("Podium: {}, {}, {}", punctaje[0], punctaje[1], punctaje[2]);
}

Rezultat

Podium: 97, 91, 88

Exemplul 2: Cele mai ieftine 2 produse

Varianta ranges primește vectorul și iteratorul de mijloc, plus o proiecție pe câmpul pret.

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

struct Produs {
    std::string nume;
    int pret;
};

int main() {
    std::vector<Produs> cos{{"Laptop", 3200}, {"Mouse", 80}, {"Monitor", 900}, {"Cablu", 25}};

    std::ranges::partial_sort(cos, cos.begin() + 2, {}, &Produs::pret);

    for (int i = 0; i < 2; ++i) {
        std::println("{}: {} lei", cos[i].nume, cos[i].pret);
    }
}