Algoritmi → Sortiranje → Sortiranje u C++: funkcija sort i poređenje

Sortiranje u C++: funkcija sort i poređenje

Osnovna upotreba

Funkcija sort(početak, kraj) sortira rastuće deo od početak do kraj (bez kraj):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int a[6] = {5, 2, 9, 1, 7, 3};
    sort(a, a + 6);                        // običan niz: od a do a + n
    for (int x : a) cout << x << " ";
    cout << endl;

    vector<int> v = {5, 2, 9, 1, 7, 3};
    sort(v.begin(), v.end());              // vektor: od begin() do end()
    for (int x : v) cout << x << " ";
    cout << endl;

    sort(v.begin(), v.end(), greater<int>());  // opadajuće
    for (int x : v) cout << x << " ";
    cout << endl;

    sort(v.begin() + 1, v.begin() + 4);    // samo elementi na pozicijama 1, 2 i 3
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

Opadajući poredak može i bez greater: sortiraj rastuće pa obrni niz sa reverse(v.begin(), v.end()).

Sopstveni kriterijum: funkcija poređenja

Trećim argumentom zadajemo funkciju koja za dva elementa x i y vraća true ako x treba da bude ispred y. Na primer, sortiranje po zbiru cifara, a kod jednakog zbira po veličini broja:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int zbirCifara(int x) {
    int s = 0;
    while (x > 0) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

// true ako x treba da bude ispred y
bool ispred(int x, int y) {
    if (zbirCifara(x) != zbirCifara(y)) return zbirCifara(x) < zbirCifara(y);
    return x < y;                           // isti zbir cifara: manji broj ide prvi
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;
    sort(v.begin(), v.end(), ispred);
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

Umesto posebne funkcije može da se napiše lambda – funkcija napisana na mestu poziva:

sort(v.begin(), v.end(), [](int x, int y) {
    return x % 10 < y % 10;    // po poslednjoj cifri
});

Sortiranje struktura i parova

Najčešći takmičarski slučaj: rang lista. Takmičare sortiramo po bodovima opadajuće, a one sa istim brojem bodova po imenu abecedno.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Takmicar {
    string ime;
    int bodovi;
};

bool bolji(const Takmicar &x, const Takmicar &y) {
    if (x.bodovi != y.bodovi) return x.bodovi > y.bodovi;  // više bodova ide prvo
    return x.ime < y.ime;                                  // pa abecedno
}

int main() {
    int n;
    cin >> n;
    vector<Takmicar> t(n);
    for (auto &x : t) cin >> x.ime >> x.bodovi;
    sort(t.begin(), t.end(), bolji);
    for (int i = 0; i < n; i++)
        cout << i + 1 << ". " << t[i].ime << " " << t[i].bodovi << endl;
    return 0;
}

Parovi (pair) se bez dodatne funkcije porede prvo po first, pa po second. Trik: ako sačuvamo par (-bodovi, ime), običan sort daje istu rang listu. Parovi su zgodni i kada treba zapamtiti originalnu poziciju elementa:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);          // (vrednost, originalna pozicija)
    for (int i = 0; i < n; i++) {
        cin >> p[i].first;
        p[i].second = i + 1;
    }
    sort(p.begin(), p.end());
    // redni brojevi elemenata od najmanjeg do najvećeg
    for (auto &x : p) cout << x.second << " ";
    cout << endl;
    return 0;
}

Stringovi, stable_sort i uklanjanje duplikata

Stringovi se porede leksikografski (kao u rečniku, po ASCII kodovima: velika slova su ispred malih, a "ab" < "abc"), pa sort nad vektorom stringova daje abecedni redosled.

stable_sort radi isto što i sort, ali čuva redosled jednakih elemenata. Kombinacija sort + unique + erase uklanja duplikate:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 1, 4, 2, 1, 4, 3};
    sort(v.begin(), v.end());                          // 1 1 2 3 4 4 4
    v.erase(unique(v.begin(), v.end()), v.end());      // unique pomera različite na početak
    for (int x : v) cout << x << " ";
    cout << endl;
    cout << "Različitih: " << v.size() << endl;
    return 0;
}

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje