Medio · ordenación

Ordenamiento burbuja

El primer algoritmo que cambia los datos en lugar de solo mirarlos. Ya sabes comparar dos números: ordenar es comparar todos los pares, en el orden correcto.

En una fraseIntercambia pares adyacentes desordenados hasta que una pasada completa no cambie nada: O(n²), y con n ≤ 1000 sobra; la salida va separada por un solo espacio.

El problema

Entrada: La primera línea es un entero n (1 ≤ n ≤ 1000). La segunda línea contiene n enteros separados por espacios.

Salida: Los mismos números en orden no decreciente, separados por un solo espacio.

Ejemplos:

Entrada	Salida
`5 5 3 8 1 9`	`1 3 5 8 9`
`1 42`	`42`
`4 7 7 2 2`	`2 2 7 7`

Ordenar en el sitio significa reordenar el array, no copiarlo a uno nuevo. Por eso el intercambio necesita una variable temporal: el error de abajo te lo muestra.

Tu solución

main.cpp — 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 — Una pasada lleva el mayor al final

Recorre el array comparando cada elemento con el siguiente. Si el de la izquierda es mayor, intercambia. Tras una pasada completa el mayor ha "burbujeado" hasta la última posición, porque gana todas las comparaciones en las que participa. Repite n−1 veces y todo queda ordenado.

Pista 2 — El bucle interno se acorta cada ronda

Después de i pasadas, los últimos i elementos ya están en su sitio. Así que el bucle interno solo necesita j < n - 1 - i. Sin el - i el resultado sigue siendo correcto, pero se desperdicia trabajo: compararías una y otra vez la cola ya ordenada.

Pista 3 — Un intercambio son tres asignaciones

int t = a[j]; a[j] = a[j+1]; a[j+1] = t;, y el orden importa. La primera línea existe solo para guardar el valor que estás a punto de sobrescribir. Si la quitas, ese valor se pierde para siempre: obtendrás un número duplicado y otro desaparecido.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1005];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

El burbuja es O(n²) y nadie lo usa en producción, pero es la demostración más clara de las dos ideas que comparten todos los algoritmos de ordenación: comparar e intercambiar. Cuando lo has escrito a mano, ordenar con la biblioteca deja de ser magia. Un ejercicio que vale la pena: añade una bandera bool swapped, actívala en cada intercambio y sal del bucle externo si una pasada entera no intercambió nada; un array ya ordenado termina entonces en una sola pasada. Ahora deja de ordenar y empieza a aprovechar el orden en Búsqueda binaria.

Análisis profundo

Por qué funciona

Compara dos vecinos e intercámbialos cuando están desordenados. Tras una pasada el mayor ha burbujeado al final, porque gana todas las comparaciones en las que participa. Repite n−1 veces y todo queda ordenado.

El coste

O(n²). Mil números son unas quinientas mil comparaciones donde quicksort necesita unas diez mil. Su valor es pedagógico, no industrial.

Dónde falla

Olvidar la temporal en el intercambio — a[j] = a[j+1]; a[j+1] = a[j]; — pone el menor en ambas posiciones y el mayor desaparece para siempre.
El límite interno importa: j < n lee a[n] fuera de rango, mientras que j < n - 1 solo es lento (recompara una cola ya ordenada), no incorrecto.

Siguiente paso

Ordenaste para poder usarlo: Búsqueda binaria descarta la mitad en cada paso.

Dos cosas para recordar

Una pasada de burbuja = el mayor queda en su sitio.
Un intercambio son tres asignaciones; la primera existe solo para no perder un valor.

🐞 Esta versión falla: ábrela y pruébala

Intercambio sin temporal: ambas posiciones toman el valor menor

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1005];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                a[j] = a[j + 1];
                a[j + 1] = a[j];
            }
        }
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}