Algoritmos de ordenación — comparación entre Bubble Sort

Un algoritmo de ordenación reorganiza los mismos elementos en un cierto orden, por ejemplo de menor a mayor. Si quieres la respuesta corta desde el principio, bubble sort es simple pero normalmente demasiado lento para listas grandes, merge sort ofrece un rendimiento fiable de $O(n \log n)$, y quick sort suele ser rápido en la práctica cuando sus particiones se mantienen razonablemente equilibradas.

La pregunta correcta no es "¿qué ordenación es mejor?", sino "¿mejor bajo qué condición?". Bubble sort enseña bien los intercambios locales, merge sort muestra con claridad la estrategia de divide y vencerás, y quick sort muestra por qué la velocidad en el caso promedio puede ser alta incluso sin garantía en el peor caso.

Qué hacen los algoritmos de ordenación

Dada una lista como $[5, 1, 4, 2]$, el algoritmo debe devolver los mismos valores en orden:

$$[1, 2, 4, 5]$$

Eso suena simple, pero distintos algoritmos llegan a ese resultado de formas muy diferentes. Las diferencias principales son:

• cómo mueven los elementos
• cuántas comparaciones o intercambios suelen usar
• cuánta memoria extra necesitan
• cuánto les afectan los patrones de entrada desfavorables

Bubble Sort: intercambios repetidos entre vecinos

Bubble sort recorre la lista e intercambia elementos adyacentes que están fuera de orden. Después de una pasada completa, el mayor elemento aún no ordenado ha "subido" hasta el final.

En $[5, 1, 4, 2]$, la primera pasada se ve así:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Luego repite el proceso sobre la parte restante no ordenada hasta que ya no hacen falta intercambios.

Bubble sort es útil sobre todo para aprender. En general, tiene complejidad temporal $O(n^2)$, así que el número de comparaciones crece rápidamente a medida que la lista se hace más grande. Para ejemplos pequeños en clase eso está bien. Para tareas reales de ordenación, normalmente no es la opción adecuada.

Merge Sort: dividir, ordenar y luego fusionar

Merge sort usa una idea de divide y vencerás. Divide la lista en partes más pequeñas, ordena esas partes y luego fusiona de nuevo los fragmentos ordenados.

Para $[5, 1, 4, 2]$, una forma clara de verlo es:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Ordena cada mitad:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Luego fusiona las dos mitades ordenadas:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

La principal ventaja de merge sort es su previsibilidad. Su tiempo de ejecución es $O(n \log n)$ en el análisis habitual, no solo en promedio. El coste principal es la memoria: las implementaciones comunes basadas en arrays usan espacio extra durante la fusión.

Quick Sort: particionar alrededor de un pivote

Quick sort también usa divide y vencerás, pero de otra manera. Elige un pivote, coloca los elementos menores a un lado y los mayores al otro, y luego ordena recursivamente ambos lados.

Usando el pivote $4$ en $[5, 1, 4, 2]$, una partición posible es:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Ahora las partes izquierda y derecha son mucho más pequeñas, así que la ordenación termina rápido.

Quick sort suele ser rápido en la práctica porque muchas implementaciones particionan in place y reducen el problema con rapidez cuando el pivote divide la lista de forma bastante equilibrada. Pero esa condición importa. Si las elecciones de pivote son repetidamente malas, por ejemplo produciendo una parte muy pequeña y otra casi completa una y otra vez, el peor caso pasa a ser $O(n^2)$.

Bubble Sort vs Merge Sort vs Quick Sort

Algoritmo	Idea central	Tiempo típico	Tiempo en el peor caso	Memoria extra
Bubble sort	Intercambios repetidos entre adyacentes	$O(n^2)$	$O(n^2)$	Baja
Merge sort	Dividir, ordenar mitades y fusionar	$O(n \log n)$	$O(n \log n)$	Mayor en implementaciones comunes con arrays
Quick sort	Particionar alrededor de un pivote	A menudo $O(n \log n)$	$O(n^2)$	A menudo menor que en merge sort

Si quieres quedarte con una idea práctica, es esta: bubble sort es un algoritmo didáctico, merge sort es la opción estable y predecible, y quick sort suele ser la elección rápida en la práctica cuando la implementación maneja bien los pivotes.

Un ejemplo resuelto con la misma lista

Usa la misma lista:

$$[5, 1, 4, 2]$$

Bubble sort sigue corrigiendo errores locales. No "ve" toda la estructura, así que puede necesitar muchas pasadas.

Merge sort primero divide el problema en piezas más pequeñas ya ordenadas y luego las combina. Esa estructura es la razón por la que su rendimiento se mantiene fiable a medida que la lista crece.

Quick sort intenta hacer una buena división desde el principio. Si la división está lo bastante equilibrada, el resto del trabajo se reduce rápido.

Por eso los estudiantes suelen recordar mejor los números de complejidad después de ver cómo una misma lista pasa por cada método. Los números no son etiquetas arbitrarias. Reflejan cómo el algoritmo reduce el desorden.

Errores comunes al comparar algoritmos de ordenación

Suponer que Quick Sort siempre es más rápido

Quick sort suele ser rápido en la práctica, pero no está garantizado que sea el más rápido en todos los casos. Un mal comportamiento del pivote puede perjudicarlo mucho.

Tratar todos los algoritmos $O(n \log n)$ como si fueran iguales

Merge sort y quick sort pueden compartir la misma tasa de crecimiento promedio sin comportarse igual en uso de memoria, garantías en el peor caso o detalles de implementación.

Usar Bubble Sort porque es fácil de programar

Que sea fácil de programar no significa que sea adecuado. Para demostraciones pequeñas, bubble sort está bien. Para entradas reales más grandes, normalmente hace trabajo innecesario.

Olvidar el modelo de entrada

Estas comparaciones suelen asumir ordenación basada en comparaciones sobre entradas generales. Si los datos tienen una estructura especial, algoritmos no basados en comparaciones como counting sort pueden cambiar por completo la decisión.

Cuándo se usa cada algoritmo de ordenación

Bubble sort se usa sobre todo para enseñanza, trazado paso a paso y ejemplos muy pequeños donde la claridad importa más que el rendimiento.

Merge sort se usa cuando importa un comportamiento consistente de $O(n \log n)$ y la memoria extra es aceptable. También encaja de forma natural con listas enlazadas y con situaciones donde importa que la ordenación sea estable, según la implementación.

Quick sort se usa cuando la velocidad práctica es importante y la implementación tiene una buena estrategia de pivote o mecanismos de protección alternativos. Muchas estrategias de ordenación de bibliotecas estándar usan ideas de quick sort junto con salvaguardas, en lugar de una versión ingenua de libro de texto.

Una forma rápida de recordar la diferencia

Recuérdalos por su movimiento:

• bubble sort corrige vecinos
• merge sort construye mitades ordenadas
• quick sort divide alrededor de un pivote

Esa imagen mental es más útil que memorizar tres nombres y tres fórmulas.

Prueba tu propia versión

Toma la lista $[7, 3, 6, 1]$ y sigue una pasada de bubble sort, un ciclo de división y fusión de merge sort, y una partición por pivote de quick sort. Si puedes explicar por qué la lista cambia de forma distinta en cada caso, entonces ya has entendido la idea.