Ordenamiento y comparadores

Tema: Greedy · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 05 de la Ruta de Aprendizaje.

Qué hace

Ordenar es la herramienta más barata que existe para revelar estructura: pone juntos los iguales, deja el mínimo y el máximo en los extremos, y habilita la búsqueda binaria. Un comparador define tu criterio de orden.

Complejidad: O(n log n) con sort. stable_sort mantiene el orden relativo de los empatados (útil cuando ya venías ordenado por otra cosa).

Cuándo usarlo

‘¿Y si lo ordeno?’ es de las primeras preguntas frente a un problema, y es el primer paso de casi todo greedy. Se aprende en el módulo 05 de la Ruta de Aprendizaje.

Implementación recomendada (C++)

#include <bits/stdc++.h>
using namespace std;
 
// Orden a medida: un comparador es una función que responde "¿va x ANTES que y?"
// (los & evitan copiar; ver la ficha Punteros y referencias, en Relacionados)
bool por_puntaje(const pair<int,string>& x, const pair<int,string>& y) {
    if (x.first != y.first) return x.first > y.first;   // puntaje descendente
    return x.second < y.second;                          // a igual puntaje, alfabético
}
 
int main() {
    vector<int> a = {93, 70, 88, 95};
    sort(a.begin(), a.end());                       // ascendente: 70 88 93 95
    sort(a.begin(), a.end(), greater<int>());       // descendente: 95 93 88 70
 
    // Por varios criterios SIN escribir comparador: mete lo que importa en un pair
    // (ordena por .first y desempata por .second).
    vector<pair<int,string>> v = {{80,"ana"},{95,"rocio"},{80,"belen"}};
    sort(v.begin(), v.end());                       // 80-ana, 80-belen, 95-rocio
 
    sort(v.begin(), v.end(), por_puntaje);          // 95-rocio, 80-ana, 80-belen
 
    // La misma función escrita donde se usa se llama *lambda*; la verás mucho:
    sort(a.begin(), a.end(), [](int x, int y) { return abs(x-90) < abs(y-90); });
    for (int x : a) cout << x << " ";               // 88 93 95 70: del más cercano a 90 al más lejano
    cout << "\n";
}

⚠️ Notas

Una lambda ([](int x, int y) { ... }) es una función anónima escrita en el lugar donde se usa: evita tener que nombrar comparadores de una sola línea. El comparador debe ser un orden estricto: x < y, nunca x <= y (con <= el sort puede caerse). Si dos elementos empatan en todos los criterios, devuelve false. La forma [](...) { ... } es una lambda: una función anónima escrita en el lugar donde se usa. Ordenar objetos grandes es caro: si solo necesitas el orden, ordena índices.

🔗 Relacionados