Reunimos Bubble, Insertion y Selection Sort para comparar su comportamiento según complejidad, cantidad de comparaciones, swaps y escenarios recomendados. Estas guías sirven para elegir rápido el algoritmo adecuado según el tamaño y el estado de los datos.
6.1 Tabla comparativa de complejidad
| Algoritmo |
Mejor caso |
Promedio |
Peor caso |
Espacio extra |
Estabilidad |
| Bubble Sort |
O(n) con corte temprano |
O(n^2) |
O(n^2) |
O(1) |
Sí |
| Insertion Sort |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
Sí |
| Selection Sort |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
No |
6.2 Rendimiento por caso
- Listas ordenadas: Insertion y Bubble (con corte) son casi lineales; Selection sigue siendo cuadrático.
- Listas inversas: los tres caen a
O(n^2); Bubble genera más swaps, Selection más comparaciones que swaps.
- Listas casi ordenadas: Insertion y Bubble aventajan claramente a Selection.
6.3 Cantidad de comparaciones
- Bubble: hasta
n(n-1)/2 en el peor caso.
- Insertion: hasta
n(n-1)/2, pero baja drásticamente si hay orden previo.
- Selection: siempre
n(n-1)/2, sin importar el orden de entrada.
6.4 Cantidad de swaps
- Bubble: puede acercarse a
n(n-1)/2 en el peor caso.
- Insertion: el desplazamiento se hace por asignación; swaps explícitos no son necesarios.
- Selection: como máximo
n - 1 intercambios, ventaja cuando el swap es costoso.
6.5 Rendimiento en memoria
Los tres trabajan in-place con espacio adicional constante (O(1)). Ninguno requiere buffers auxiliares grandes.
6.6 Cuándo usar cada uno
- Bubble: para enseñanza o listas muy pequeñas/casi ordenadas donde el corte temprano ahorra tiempo.
- Insertion: mejor opción para entradas casi ordenadas o como paso final de algoritmos híbridos.
- Selection: cuando el costo de swap es alto pero comparar es barato, y la estabilidad no importa.
6.7 Ejemplos con arrays de distintos tamaños
Comparación cualitativa usando la misma familia de datos:
- n = 10, casi ordenado: Insertion completa en pocas operaciones; Bubble se beneficia del corte; Selection realiza comparaciones completas.
- n = 100, aleatorio: los tres son cuadráticos; Selection hace menos swaps, Bubble y Insertion más movimiento.
- n = 1000, inverso: todos tardan demasiado; conviene migrar a un algoritmo
O(n log n) (por ejemplo, quicksort o mergesort).