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 ordenardespué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}:

514285 > 1: intercambia1154285 > 4: intercambia2145285 > 2: intercambia3142585 < 8: se quedan414258fin de la pasada: el 8 ya está en su lugarla pasada 2 hace lo mismo hasta la penúltima casilla; n−1 pasadas dejan todo ordenado

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.

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.

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):

#ProblemaFaseQué practica
1¿Cuántas poleras de cada talla?Nacional 2025ordenar y agrupar de a 10
2Papas fritasRegional 2023ordenar descendente y saltar de a n
3Parejas para el tangoRegional 2015recorrer dos listas ordenadas en paralelo
4⭐ OcimaticRegional 2016el poder de ordenar por (a, −b)

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Helpful Maths (339A)★ (800)ordenar caracteres de un string
2Next Round (158A)★ (800)datos ya ordenados: aprovecharlo
3Twins (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?


← 04 - Matrices · Ruta de Aprendizaje · 06 - Conjuntos, mapas y pares →