Ordenação [Pt 3]: Função Sort (C++)

A maior parte das vezes, só queremos que o vetor esteja ordenado. Se for uma variável já existente de C++ (int, double, string etc), para a qual já existe um comparador padrão (dado dos inteiros ou duas strings, é possível comparar), basta chamar a função pro vetor.

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

vector <char> v_char; //Vector de char
vector <string> v_str; //Vector de strings
int v_int[1000]; //Vetor de inteiros

int main() {
    int n; //n = tamanho do vetor

    sort(v_char.begin(), v_char.end());
    //Soh ordenar n elementos
    sort(v_str.begin(), v_str.begin() + n);
    sort(v_int, v_int + n);
}

Se quisermos ordenar em outra ordem ou ordenar um vetor de structs (não é trivial comparar), precisamos criar uma função de comparação. Um exemplo qualquer:

#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;

struct node {
    int v_int;
    vector <char> p;
    double v_double;
};

node vetor[25];

//Se compare retorna true, quer dizer que jah ta na ordem certa
bool compare(const node &s1, const node &s2) {
    //O criterio que eu quero que seja usado
    //Quero que o maior double fique na frente
    if(s1.v_double != s2.v_double) return s1.v_double > s2.v_double;
    /*Isso eh equivalente a:
    if(a > b) return true;
    else if(a < b) return false; */
    
    //Se os dois doubles forem iguais
    else if(s1.v_int != s2.v_int) {
        //Se A inteiro eh par, quero que ele fique na frente
        if(s1.v_int%2 == 0) return true;
        else return false;
    }

    //Se nao fica na frente quem tem mais chars no vetor
    else return s1.p.size() > s2.p.size();
}

int main() {
    vetor[0].v_int = 3; vetor[0].v_double = 2.0; vetor[0].p.push_back('a');
    vetor[1].v_int = 3; vetor[1].v_double = 3.0;
    vetor[2].v_int = 2; vetor[2].v_double = 2.0;
    vetor[3].v_int = 3; vetor[3].v_double = 3.0; vetor[3].p.push_back('b');
    sort(vetor, vetor + 4, compare);
    for(int i = 0; i < 4; i++) {
        printf("%d %lf %lu\n", vetor[i].v_int,
                vetor[i].v_double, vetor[i].p.size());
    }
    return 0;
}

É possível também redefinir o operador de comparação. As funções usam o < ("menor que") para comparar, ou seja, para saber se deve trocar A com B, o compilador checa se A < B e se B < A. No caso de A == B, pode ser que ele troque ou não (arbitrário). Em alguns casos, é necessário definir um operador, como quando criamos uma priority_queue (fila de prioridade) em que a comparação não é trivial.

#include <queue>
#include <vector>
#include <stdio.h>
using namespace std;

struct novo_int {
    int val;

    bool operator < (const novo_int& i) const{
        return val > i.val;
    }
};

int main() {
    priority_queue<novo_int> pq;
    int aux;
    while(true) {
        novo_int tmp;

        scanf("%d", &tmp.val);
        pq.push(tmp);
        //Checando quem esta no topo de pq
        printf("%d\n", pq.top().val);
    }
}

Uma variação é o stable_sort, que, no caso A == B, mantém na frente quem já está na frente.

Problemas relacionados:
URI 1244: Ordenação por Tamanho [link]
URI 1252: Sort! Sort!! e Sort!!! [link]

Códigos no github [link].