`std::nth_element` în C++

Pune pe poziția n elementul care ar fi acolo după sortare; util pentru mediană sau al k-lea cel mai mic.

Sintaxă

void nth_element(RandomIt first, RandomIt nth, RandomIt last);
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

Ce face `std::nth_element`

După std::nth_element, elementul de pe poziția nth este exact cel care ar ajunge acolo dacă ai sorta tot intervalul. Toate elementele din stânga lui sunt mai mici sau egale, toate din dreapta sunt mai mari sau egale, dar nu în ordine.

Lucrează în timp liniar în medie, mult mai repede decât o sortare completă. Este metoda obișnuită pentru mediană.

Parametri

Parametru	Descriere
`first, last`	Intervalul.
`nth`	Poziția care trebuie să primească elementul corect.
`comp`	Opțional. Funcția de comparare.

Ce returnează

Nimic.

Exemple

Exemplul 1: Mediana unor salarii

Pentru 7 valori, mediana este elementul de pe poziția 3 (a patra valoare în ordine).

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

int main() {
    std::vector<int> salarii{4200, 3100, 8900, 5000, 3600, 12000, 4700};

    auto mijloc = salarii.begin() + salarii.size() / 2;
    std::nth_element(salarii.begin(), mijloc, salarii.end());

    std::println("Salariul median: {} lei", *mijloc);
}

Rezultat

Salariul median: 4700 lei

Exemplul 2: Al doilea cel mai mic număr

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

int main() {
    std::vector<int> v{9, 4, 7, 1, 8, 2};

    std::ranges::nth_element(v, v.begin() + 1);
    std::println("Al doilea cel mai mic: {}", v[1]);
}