05 · Ordenamiento
Aprender a programar · Ruta de Aprendizaje
Antes de empezar. Vectores, índices y ciclos: 03 - Arreglos y búsqueda lineal. Aquí también se introduce pair antes de ordenarlo.
🎯 Objetivos
Al terminar este módulo sabes:
- Qué hace un algoritmo de ordenamiento por dentro (bubble sort).
- Usar
sort()para lo que de verdad importa: competir. - Ordenar pares y strings, ascendente y descendente.
📖 La lección
Por qué ordenar
Muchos problemas se vuelven triviales con los datos ordenados: el mínimo queda primero, el máximo al final, los repetidos quedan juntos, y la búsqueda binaria (módulo 08) se vuelve posible. “¿Y si lo ordeno?” es de las primeras preguntas que hay que hacerse frente a un problema.
Detectar un repetido. En {7,2,5,2}, comparar cada pareja funciona, pero repite muchas comparaciones. Ordenar produce {2,2,5,7}: si un valor se repite, sus copias quedan juntas. Basta comparar vecinos. Después de ordenar, cada elemento solo necesita compararse con su vecino; ya no con todos los demás. El módulo 07 enseñará a comparar sus costos.
Ordenar cambia las posiciones. Si debes responder la posición original, guarda (valor, índice_original) y mueve el par completo. Si la pregunta depende del orden de llegada, comprueba antes si puedes perderlo.
La herramienta real: sort()
vector<int> a = {5, 1, 4, 2, 8};
sort(a.begin(), a.end()); // ascendente: 1 2 4 5 8
sort(a.begin(), a.end(), greater<int>()); // descendente: 8 5 4 2 1
string s = "competencia";
sort(s.begin(), s.end()); // ¡también ordena strings!sort() es la herramienta habitual para ordenar listas grandes. Su costo se describe como O(n log n); podrás interpretar esa notación en el módulo 07. Para usarlo aquí basta saber qué orden produce y que evita la comparación de todas las parejas.
Sobre ese a.begin(), a.end(): son la forma de decir “desde el principio
hasta el final” — o sea, todo el vector. Son iteradores: begin()
apunta al primer elemento y end() a la posición posterior al último.
El segundo extremo queda excluido; no se puede leer como un elemento.
Muchas funciones de la biblioteca usan esa misma convención.
Del orden a una respuesta: detectar repetidos
En {7,2,5,2}, ordenar da {2,2,5,7}. Comparamos posiciones 0 y 1,
luego 1 y 2, y así sucesivamente. Cualquier valor repetido forma un bloque
continuo; por eso al menos dos de sus copias quedan juntas.
vector<int> a = {7, 2, 5, 2};
sort(a.begin(), a.end());
bool repetido = false;
for (int i = 1; i < (int)a.size(); i++)
if (a[i] == a[i - 1]) { repetido = true; break; }
cout << (repetido ? "SI" : "NO") << "\n";Imprime SI. Si hay cero o un elemento, el ciclo no entra y responde NO.
El vector sí cambia de orden; conserva una copia si necesitas el original.
Ordenar pares
Un pair<T, U> reúne dos datos en una unidad. Por ejemplo,
pair<int, string> jugador = {7, "ana"} guarda puntos y nombre:
jugador.first vale 7 y jugador.second vale "ana". Un
vector<pair<int, string>> es una lista de esos registros. Al ordenarla,
los puntos y el nombre de cada jugador se mueven juntos.
Un pair se ordena por .first, y desempata por .second — gratis:
// supone: int n; // ya leído
vector<pair<int,string>> puntaje(n); // (puntos, nombre)
for (int i = 0; i < n; i++)
cin >> puntaje[i].first >> puntaje[i].second;
sort(puntaje.begin(), puntaje.end());| antes de ordenar | después |
|---|---|
| (7, “ana”) | (7, “alma”) |
| (9, “beto”) | (7, “ana”) |
| (7, “alma”) | (9, “beto”) |
Los dos 7 quedan juntos y, entre ellos, decide el nombre. ¿Y si quieres el
puntaje descendente pero el nombre ascendente? Guarda -puntos en
.first, siempre que su negación quepa en el tipo. El mínimo int de 32 bits no puede negarse dentro de ese mismo tipo; convierte antes a long long o usa un comparador. Negar una de las dos componentes para invertir solo ese
criterio —ordenar por (a, −b)— es exactamente el truco que pide Ocimatic en
la práctica.
La ficha de referencia, con los comparadores propios y la regla del orden estricto, es Ordenamiento y comparadores.
Este truco — “mete lo que te importa en .first” — resuelve la mayoría de
los “ordena por X y desempata por Y” sin escribir comparadores.
Cómo funciona por dentro: bubble sort
Esta ampliación explica un algoritmo sencillo; no necesitas programarlo para usar sort.
Compara vecinos y los intercambia si están al revés; el mayor “burbujea” al final en cada pasada:
// supone: int n; vector<int> a; // el arreglo a ordenar
for (int pasada = 0; pasada < n - 1; pasada++)
for (int i = 0; i + 1 < n - pasada; i++)
if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);Mira la primera pasada sobre {5, 1, 4, 2, 8}:
Si el diagrama no cabe, deslízalo horizontalmente.
Cada pasada deja el mayor de lo que queda en su lugar definitivo; por eso el
ciclo interior llega cada vez menos lejos (n - pasada), y n−1 pasadas
bastan. Para n elementos, esta versión compara (n−1)+(n−2)+…+1 parejas.
Con cinco son diez; con mil, 499500. Esa cantidad crece aproximadamente
como el cuadrado de n: por eso no es una buena elección para listas grandes.
El módulo 07 formaliza esa comparación.
🏋️ Práctica
Práctica directa: ¿Se repite algún valor?
Lee n (0 a 100) y n enteros. Imprime SI si hay repetidos, NO si no. Entrada: 4 / 7 2 5 2. Salida: SI.
En los ejemplos de entrada y salida, / separa líneas; no se escribe en el archivo.
Idea para comprobar tu solución
Tras ordenar quedan 2,2,5,7: comparar vecinos basta. Para n=0 o n=1 no hay pareja que comparar y la salida es NO.
Variación: Hasta dónde alcanza
Hay n productos, cada uno comprable una vez, con precios positivos. Con presupuesto B, imprime la mayor cantidad que puedes comprar. Para precios {7,2,5,2} y B=9, la respuesta es 3.
Una pista, si la necesitas
¿Podría mejorar la cantidad si sustituyes un producto elegido por otro más barato?
Contrastar el razonamiento
Ordena de menor a mayor y toma mientras alcance. Los k más baratos tienen suma mínima entre todas las selecciones de k productos; si no caben, ninguna selección de k cabe.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | ¿Cuántas poleras de cada talla? | Nacional 2025 | ordenar y agrupar de a 10 |
| 2 | Papas fritas | Regional 2023 | ordenar descendente y saltar de a n |
| 3 | Parejas para el tango | Regional 2015 | recorrer dos listas ordenadas en paralelo |
| 4 | ⭐ Ocimatic | Regional 2016 | el poder de ordenar por (a, −b) |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Helpful Maths (339A) | ★ (800) | ordenar caracteres de un string |
| 2 | Next Round (158A) | ★ (800) | datos ya ordenados: aprovecharlo |
| 3 | Twins (160A) | ★★ (900) | ordenar descendente + acumular |
| 4 | ⭐ Laptops (456A) | ★★★ (1100) | ordenar pares y razonar sobre el resultado |
Un ejemplo para pensar
Hay tres participantes: Ana tiene 8 puntos, Beto tiene 10 y Alma tiene 8.
Se pide ordenar por puntos de mayor a menor y, en empate, por nombre de
menor a mayor. ¿Sirve ordenar los pares (puntos, nombre) y luego invertirlos?
Invertir todo también invierte el desempate
El orden pedido es Beto, Alma, Ana. Ordenar los pares ascendentemente da Alma, Ana, Beto; invertirlos da Beto, Ana, Alma, con el empate al revés. Guardar
(-puntos, nombre)y ordenar ascendentemente produce(-10, Beto),(-8, Alma),(-8, Ana): solo se invirtió el criterio de los puntos.
← 04 - Matrices · Ruta de Aprendizaje · 06 - Conjuntos, mapas y pares →