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.