Medio · conteo por cubos
Ordenación por conteo
Ordenaste con burbuja comparando pares. Esta no compara nada, y no es un truco: es otro intercambio. Memoria y un rango de valores conocido a cambio de velocidad.
En una fraseCada valor está entre 0 y 100, así que cuenta apariciones en un array de 101 posiciones y reimprime los valores en orden: O(n + 101) en vez de O(n log n).
El problema
Entrada: La primera línea es un entero n (1 ≤ n ≤ 1000). La segunda línea contiene n enteros separados por espacios, cada uno entre 0 y 100 inclusive.
Salida: Los mismos números en orden no decreciente, separados por un solo espacio.
Ejemplos:
| Entrada | Salida |
|---|---|
5 | 1 3 5 8 9 |
4 | 2 2 7 7 |
3 | 0 50 100 |
El rango 0–100 no es un detalle: es la precondición. La ordenación por conteo solo funciona porque puedes permitirte un contador por cada valor posible. Con valores de hasta mil millones necesitarías mil millones de contadores.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Ya usaste un array de conteo
Frecuencia de dígitos hacía exactamente esto: un array donde el índice es el valor y el elemento es cuántas veces aparece. Ordenar es solo leer ese array de izquierda a derecha.
Pista 2 — Dos bucles anidados, ninguno compara
Bucle externo v de 0 a 100. El interno se ejecuta cnt[v] veces, imprimiendo v cada vez. Si un valor apareció cuatro veces, lo imprimes cuatro veces; si nunca apareció, el interno se ejecuta cero veces: no hace falta ningún if.
Pista 3 — El bug que parece correcto con valores distintos
Imprimir cada valor una sola vez, ignorando su conteo, da una respuesta perfecta cuando todas las entradas son distintas: pasa el primer ejemplo y falla en cuanto algo se repite. Prueba con 7 7 2 2 antes de fiarte de tu código.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int cnt[101] = {0};
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
for (int v = 0; v <= 100; v++) {
for (int k = 0; k < cnt[v]; k++) cout << v << " ";
}
cout << endl;
return 0;
}La ordenación por conteo es O(n + k), con k el rango de valores: más rápida que cualquier ordenación por comparación, que no puede bajar de O(n log n). No viola esa cota: la cota solo aplica a algoritmos que aprenden de los datos mediante comparaciones. Aquí aprendes de los valores mismos. Los sistemas reales lo usan en todas partes: ordenar edades, puntuaciones, valores de píxel o bytes. Ahora, el primer problema realmente recursivo del conjunto: Torres de Hanói.
Análisis profundo
Por qué funciona
Haz que el índice sea el valor y el elemento el número de apariciones; ordenar pasa a ser leer ese array de izquierda a derecha.
El coste
O(n + k) con k el rango de valores. Más rápida que cualquier ordenación por comparación, porque la cota O(n log n) solo restringe a los algoritmos que aprenden de los datos <em>mediante comparaciones</em>, y tú aprendes de los valores mismos.
Dónde falla
- Imprimir cada valor una sola vez ignorando su conteo es perfecto cuando todas las entradas son distintas, y falla en cuanto algo se repite.
- Olvidar poner a cero el array de conteo (
int cnt[101] = {0};) acumula sobre la basura que hubiera.
Siguiente paso
El primer problema realmente recursivo: Torres de Hanói.
Dos cosas para recordar
- Índice es el valor, elemento es el conteo: ordenar se vuelve leer.
- Es rápida porque el rango es pequeño. Eso es una precondición, no un detalle.
🐞 Esta versión falla: ábrela y pruébala
Imprime cada valor una vez: correcto solo cuando nada se repite
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int cnt[101] = {0};
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
for (int v = 0; v <= 100; v++) {
if (cnt[v] > 0) cout << v << " ";
}
cout << endl;
return 0;
}