Ordenamiento de burbuja
Recorre la lista una y otra vez e intercambia los vecinos que están en el orden incorrecto. Tras cada pasada, el mayor valor restante queda al final.
- mejor caso Ω(n)
- caso medio Θ(n²)
- peor caso O(n²)
- espacio O(1)
- estable
- sin memoria extra
¿Qué significan estos términos?
- Mejor caso: cómo crece el tiempo con el tamaño n de la lista cuando la entrada es la más fácil para este algoritmo.
- Caso medio: cómo suele crecer el tiempo con n. Con n², el doble de valores tarda unas cuatro veces más; n log n crece mucho más despacio.
- Peor caso: el crecimiento con la entrada más difícil. Útil cuando la velocidad nunca debe caer.
- Espacio: cuánta memoria extra hace falta además de la lista. 1 son unas pocas variables; n, una copia de la lista.
- Estable: dos valores iguales conservan su orden original. Importa al ordenar registros por un solo campo.
- Sin memoria extra: ordena dentro de la propia lista, sin una segunda lista.
- comparando
- moviendo
- en su lugar final
Pulsa reproducir: las líneas muestran cómo crece el coste
Pulsa reproducir o avanza paso a paso.
Espacio: reproducir o pausar. Flechas izquierda y derecha: paso a paso. Inicio y Fin: saltar.
Prueba esto: Elige una lista casi ordenada. Tras una pasada sin intercambios, el algoritmo se detiene antes.
Cómo funciona
Compara dos vecinos cada vez y los intercambia si el de la izquierda es mayor. Así, en cada pasada el mayor valor avanza hasta el extremo derecho, como una burbuja que sube. Si una pasada no hace ningún intercambio, la lista ya está ordenada.
Cuándo es una buena opción
Casi nunca en programas reales, porque es lento con listas largas. Para aprender es ideal: muestra la idea básica de ordenar comparando e intercambiando. Solo es rápido si la lista ya está ordenada.