Ordenação em C++: std::sort, comparadores personalizados e ordenação estável

Ordenar é só mais um algoritmo

Na página anterior você viu que a biblioteca padrão traz algoritmos prontos que funcionam sobre qualquer intervalo por meio de iteradores. A ordenação é a que você mais vai usar, e ela ganha sua própria página porque tem algumas arestas afiadas: ordens personalizadas, estabilidade e uma regra que, se você quebrar, entrega comportamento indefinido em vez de uma resposta errada.

O cavalo de batalha é o std::sort de <algorithm>. Você dá a ele o início e o fim de um intervalo, e ele reorganiza os elementos no lugar em ordem crescente:

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end());   // crescente, no lugar

    for (int n : nums) cout << n << " ";  // 1 2 3 5 8 9
    cout << "\n";
    return 0;
}

Nenhuma cópia é feita: o próprio vetor é reordenado. Por baixo dos panos, o std::sort costuma ser um introsort (quicksort que recorre ao heapsort), dando O(n log n) em média. Isso é quase sempre mais rápido e muito menos propenso a erros do que escrever sua própria ordenação.

Também funciona com arrays C puros: você só descreve o intervalo com ponteiros:

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

int main() {
    int arr[] = {40, 10, 30, 20};
    int n = 4;

    sort(arr, arr + n);               // ou sort(begin(arr), end(arr));

    for (int x : arr) cout << x << " ";  // 10 20 30 40
    return 0;
}

Ordem personalizada com um comparador

Por padrão, o std::sort ordena os elementos com operator<. Para ordenar de outra forma, passe um terceiro argumento: um comparador que recebe dois elementos e retorna true se o primeiro deve vir antes do segundo.

Uma lambda é o encaixe natural. A ordem decrescente é só a > b:

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

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;   // "a antes de b" quando a é maior -> decrescente
    });

    for (int n : nums) cout << n << " ";  // 9 8 5 3 2 1
    cout << "\n";
    return 0;
}

Para o caso comum de ordem decrescente pura sobre tipos embutidos, a biblioteca ainda traz um comparador pronto, o greater<T>() de <functional>:

#include <functional>
sort(nums.begin(), nums.end(), greater<int>());  // igual a a > b

O comparador também é a forma de ordenar por algo diferente do próprio valor; por exemplo, ordenar strings por comprimento em vez de alfabeticamente:

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

int main() {
    vector<string> words = {"pear", "fig", "banana", "kiwi"};

    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.size() < b.size();   // palavras mais curtas primeiro
    });

    for (const string& w : words) cout << w << " ";  // fig kiwi pear banana
    cout << "\n";
    return 0;
}

Receba os parâmetros do comparador por const& para qualquer coisa maior que alguns bytes (como string): copiar cada elemento a cada comparação é puro desperdício.

Ordenar structs por um campo

Em programas reais você geralmente ordena coleções de structs por um de seus campos. O comparador simplesmente acessa o campo que importa. Aqui ordenamos pessoas por idade, da mais nova primeiro:

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

struct Person {
    string name;
    int age;
};

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age < b.age;
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    return 0;
}

Repare que Linus e Dennis têm ambos 25 anos. Aqui eles saíram na ordem relativa original, mas o std::sort não garante isso. Se a ordem relativa de elementos iguais importa, use o std::stable_sort, que a preserva (a um pequeno custo de desempenho):

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    stable_sort(people.begin(), people.end(),
        [](const Person& a, const Person& b) { return a.age < b.age; });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";
    // Linus continua antes de Dennis: a ordem de entrada é preservada
    return 0;
}

Para desempatar de forma deliberada (por exemplo, ordenar por idade e depois alfabeticamente por nome), compare a chave secundária só quando as chaves primárias forem iguais. O std::tie deixa isso limpo:

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

struct Person { string name; int age; };

int main() {
    vector<Person> people = {
        {"Ada", 36}, {"Linus", 25}, {"Grace", 41}, {"Dennis", 25}
    };

    sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return tie(a.age, a.name) < tie(b.age, b.name);  // idade, depois nome
    });

    for (const Person& p : people)
        cout << p.name << " (" << p.age << ")\n";  // Dennis e Linus 25, alfabético
    return 0;
}

A armadilha da ordenação fraca estrita

Este é o erro mais perigoso na ordenação em C++, porque ele não te dá uma resposta errada: ele dá comportamento indefinido, que muitas vezes significa um travamento ou uma leitura fora dos limites.

O std::sort exige que seu comparador defina uma ordenação fraca estrita. A regra prática: comp(x, x) deve ser false para qualquer elemento x. Em outras palavras, um elemento nunca está "antes" de si mesmo. É exatamente isso que < e > te dão, e exatamente o que <= e >= quebram:

// BUG: retorna true quando a == b, violando a ordenação fraca estrita.
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // comportamento indefinido: pode travar com algumas entradas
});

Com <=, o comparador afirma que 5 vem antes de outro 5, o que é contraditório. O std::sort pode então percorrer um ponteiro além do fim do intervalo. Entradas pequenas às vezes parecem funcionar, o que torna este bug aterrorizante: ele pode passar nos seus testes e travar em produção. A correção é simplesmente <:

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

    sort(v.begin(), v.end(), [](int a, int b) {
        return a < b;   // correto: false quando iguais
    });

    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Um segundo problema clássico: ordenar invalida qualquer coisa que aponte para dentro do intervalo. Iteradores, ponteiros e índices que você salvou antes da ordenação já não se referem ao mesmo elemento lógico depois, porque os elementos se moveram. Refaça qualquer posição de que você precise depois de ordenar, nunca antes.

Ordenar parte de um intervalo

Às vezes você não precisa de tudo ordenado: você só quer os primeiros elementos. Ordenar o vetor inteiro para ler os três primeiros é desperdício. O std::partial_sort organiza apenas os elementos que você pedir e deixa o resto em ordem não especificada, o que é mais barato:

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};

    // Coloca os 3 menores, em ordem, no início. O resto fica não especificado.
    partial_sort(v.begin(), v.begin() + 3, v.end());

    for (int i = 0; i < 3; i++) cout << v[i] << " ";  // 1 2 3
    cout << "\n";
    return 0;
}

E se você só precisa do único elemento que estaria em uma dada posição (como a mediana), o std::nth_element faz ainda menos trabalho: ele coloca o elemento certo nesse índice, com tudo o que é menor antes e tudo o que é maior depois, tudo em O(n) em média.

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    size_t mid = v.size() / 2;

    nth_element(v.begin(), v.begin() + mid, v.end());

    cout << "median is " << v[mid] << "\n";  // 5
    return 0;
}

Recorra a esses quando "totalmente ordenado" for mais do que o problema realmente precisa: eles economizam tempo de verdade em grandes volumes de dados.

Próximo: Templates

Você reparou que o mesmo std::sort lidou com int, string e seu próprio struct Person, e que greater<int>() poderia ser tão facilmente greater<string>()? Essa generalidade não é mágica: são os templates, o mecanismo que permite que um único pedaço de código funcione para qualquer tipo que o chamador conectar. Na próxima página veremos como escrever suas próprias funções e classes com templates, para que seu código possa ser tão agnóstico em relação ao tipo quanto os algoritmos que você vem usando.