`sort`, `lower_bound`, `upper_bound`

Biblioteca <algorithm> conține funcții puternice pentru sortare și căutare pe vectori. Acestea sunt cele mai folosite funcții STL la concursuri.

#include <algorithm>

`sort` - sortarea

vector<int> v = {3, 7, 2, 9, 4};

sort(v.begin(), v.end());   // crescător: 2 3 4 7 9

Pe vector clasic:

int v[] = {0, 3, 7, 2, 9, 4}; // indexat de la 1
int n = 5;

sort(v + 1, v + n + 1);     // sortează v[1] ... v[n]

Complexitate: O(n log n)

sort din STL folosește Introsort (combinație de QuickSort, HeapSort și InsertionSort) - garantat O(n log n).

Sort descrescător

sort(v.begin(), v.end(), greater<int>());
// 9 7 4 3 2

Sort cu comparator custom

Putem defini propria regulă de sortare:

bool cmp(int a, int b) {
    return a > b;   // descrescător
}

sort(v.begin(), v.end(), cmp);

Sortare după ultima cifră

bool cmp(int a, int b) {
    return a % 10 < b % 10;
}

vector<int> v = {23, 15, 42, 31, 18};
sort(v.begin(), v.end(), cmp);
// 31 42 23 15 18 (ordonate după ultima cifră: 1, 2, 3, 5, 8)

Sortare structuri

struct Elev {
    char nume[50];
    int nota;
};

bool cmp(Elev a, Elev b) {
    return a.nota > b.nota;  // descrescător după notă
}

Elev elevi[101];
int n;

sort(elevi, elevi + n, cmp);

Sortare perechi

pair se sortează automat: întâi după .first, apoi după .second:

vector<pair<int,int>> v = {{3,5}, {1,7}, {3,2}, {1,3}};
sort(v.begin(), v.end());
// {1,3}, {1,7}, {3,2}, {3,5}

`stable_sort`

sort nu garantează ordinea relativă a elementelor egale. stable_sort o păstrează:

stable_sort(v.begin(), v.end(), cmp);

Util când sortăm după un criteriu dar vrem să păstrăm ordinea originală pentru elemente egale.

`lower_bound` - primul element >= x

Pe un vector sortat, lower_bound găsește primul element mai mare sau egal cu x în O(log n).

vector<int> v = {1, 3, 5, 7, 9, 11};

auto it = lower_bound(v.begin(), v.end(), 5);
cout << *it;         // 5 (primul >= 5)
cout << it - v.begin(); // 2 (indexul)

auto it2 = lower_bound(v.begin(), v.end(), 6);
cout << *it2;        // 7 (primul >= 6, deoarece 6 nu există)

Pe vector clasic:

int v[] = {0, 1, 3, 5, 7, 9, 11}; // indexat de la 1
int poz = lower_bound(v + 1, v + n + 1, 5) - v;
// poz = 3 (poziția lui 5, indexat de la 1)

`upper_bound` - primul element > x

Ca lower_bound, dar strict mai mare:

vector<int> v = {1, 3, 5, 7, 9, 11};

auto it = upper_bound(v.begin(), v.end(), 5);
cout << *it;  // 7 (primul strict > 5)

Diferența

	`lower_bound(x)`	`upper_bound(x)`
Caută	Primul >= x	Primul > x
Dacă x există	Pointează la x	Pointează după x
Dacă x nu există	Primul mai mare	Primul mai mare

Aplicații clasice

Numărarea aparițiilor unei valori

auto lo = lower_bound(v.begin(), v.end(), x);
auto hi = upper_bound(v.begin(), v.end(), x);
int cnt = hi - lo;  // numărul de apariții ale lui x

Verificare existență

bool exista = binary_search(v.begin(), v.end(), x);

binary_search returnează true/false, nu poziția.

Inserare în poziția corectă (vector sortat)

auto poz = lower_bound(v.begin(), v.end(), x);
v.insert(poz, x); // inserează x păstrând vectorul sortat

Exemplu complet: câte elemente din B se găsesc în A?

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int n, m;
    fin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) fin >> a[i];

    sort(a.begin(), a.end());

    fin >> m;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int x;
        fin >> x;
        if (binary_search(a.begin(), a.end(), x))
            cnt++;
    }

    fout << cnt;

    return 0;
}

`nth_element` - al k-lea element

Găsește al k-lea cel mai mic element în O(n) fără a sorta tot vectorul:

vector<int> v = {3, 7, 2, 9, 4};

nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] conține al 3-lea cel mai mic element (4)
// elementele înainte sunt mai mici, cele după sunt mai mari
// DAR nu sunt neapărat sortate

Util când vrem doar mediana sau al k-lea element fără sort complet.

`partial_sort` - sortare parțială

Sortăm doar primele K elemente:

vector<int> v = {3, 7, 2, 9, 4, 1, 8};

partial_sort(v.begin(), v.begin() + 3, v.end());
// Primele 3: 1 2 3 (sortate), restul: negarantat

Mai rapid decât sort complet când K e mic.

Tabel rezumativ

Funcție	Ce face	Complexitate
`sort(begin, end)`	Sortare crescătoare	O(n log n)
`sort(begin, end, cmp)`	Sortare custom	O(n log n)
`stable_sort(begin, end)`	Sortare stabilă	O(n log n)
`lower_bound(begin, end, x)`	Primul >= x	O(log n)
`upper_bound(begin, end, x)`	Primul > x	O(log n)
`binary_search(begin, end, x)`	Există x?	O(log n)
`nth_element(begin, nth, end)`	Al k-lea element	O(n)
`partial_sort(begin, mid, end)`	Sortare primele K	O(n log K)

Greșeli frecvente

1. `lower_bound` pe vector nesortat

// GREȘIT - vectorul TREBUIE sortat!
lower_bound(v.begin(), v.end(), 5); // rezultat imprevizibil

2. Comparator inconsistent

bool cmp(int a, int b) {
    return a <= b;  // GREȘIT - trebuie strict <, nu <=
}

Comparatorul trebuie să returneze true doar când a e strict mai mic decât b. Cu <=, sort poate intra în buclă infinită.

3. Uitarea lui `- v.begin()` pentru index

auto it = lower_bound(v.begin(), v.end(), x);
int index = it - v.begin(); // CORECT
int index = *it;             // GREȘIT - asta e valoarea, nu indexul

Ce să reții

sort: O(n log n), crescător implicit, custom cu comparator.
lower_bound(x): primul >= x, upper_bound(x): primul > x. Ambele O(log n).
Funcționează doar pe vectori sortați.
binary_search: verifică existența (true/false).
nth_element: al k-lea element fără sort complet, O(n).
Comparatorul trebuie să fie strict (<, nu <=).

sort, lower_bound, upper_bound

sort - sortarea