GUÍA 18-11-26 Estructuras de Datos

CN122 · miércoles 18/11/2026 · 13:00-14:15 · Sesión 28

Métodos de ordenamiento sobre arreglos (1/3)

EL PROBLEMA

Ordenar es la operación más estudiada de la computación. Interesa porque habilita la búsqueda binaria, porque aparece en todos lados y porque su análisis enseña a comparar algoritmos.

CRITERIOS DE COMPARACIÓN

• Complejidad en el mejor caso, promedio y peor caso.
• Memoria adicional: in situ si es O(1).
• Estabilidad: si conserva el orden relativo de elementos con clave igual.
• Adaptabilidad: si aprovecha que los datos ya estén parcialmente ordenados.

La estabilidad importa más de lo que parece. Al ordenar registros por un segundo criterio, solo un algoritmo estable conserva el primero.

ORDENAMIENTO BURBUJA

Compara pares adyacentes y los intercambia. En cada pasada el mayor «burbujea» hasta el final.

• O(n²) en promedio y en el peor caso; O(n) en el mejor si se detecta que no hubo intercambios.
• In situ y estable.
• Es el más lento de todos en la práctica; se estudia por claridad, no por utilidad.

ORDENAMIENTO POR SELECCIÓN

Busca el mínimo del resto y lo coloca en su posición. Hace exactamente n−1 intercambios, el mínimo posible.

• O(n²) siempre, incluso si el arreglo ya está ordenado.
• In situ, no estable en su versión con intercambio.
• Útil cuando escribir en memoria es caro, porque minimiza los movimientos.

ORDENAMIENTO POR INSERCIÓN

Toma cada elemento y lo inserta en su lugar dentro de la parte ya ordenada, como se acomoda una mano de cartas.

• O(n²) en el peor caso, pero O(n) si el arreglo está casi ordenado.
• In situ, estable y adaptable.
• Es el mejor de los tres cuadráticos y se usa de verdad: los algoritmos O(n log n) cambian a inserción para subarreglos pequeños.

PRÁCTICA

Implementar los tres contando comparaciones e intercambios, con arreglos aleatorios, ordenados y en orden inverso.