GUÍA 25-11-26 Estructuras de Datos

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

Métodos de ordenamiento sobre arreglos (3/3) · Cierre del curso

ÚLTIMO DÍA DE CLASES

Hoy, 25 de noviembre, cierra el curso. Los exámenes finales se aplican en el periodo del 1 al 8 de diciembre.

HEAPSORT

Construye un montículo con el arreglo y extrae repetidamente el máximo, colocándolo al final. Reutiliza el montículo de la sesión 13.

• O(n log n) garantizado, igual que merge sort.
• In situ, a diferencia de merge sort.
• No estable, y en la práctica algo más lento que quicksort por peor localidad de caché.

LA COTA INFERIOR

Cualquier algoritmo de ordenamiento basado en comparaciones necesita al menos Ω(n log n) comparaciones. La demostración usa un árbol de decisión: con n! resultados posibles, el árbol tiene altura mínima log(n!), que es Θ(n log n).

No es una limitación de los algoritmos conocidos: es un límite matemático. Ningún algoritmo por comparaciones puede ser mejor.

ORDENAMIENTOS QUE NO COMPARAN

• Counting sort — cuenta ocurrencias; O(n+k) con k el rango de valores.
• Radix sort — ordena dígito por dígito; O(d·n).

Rompen la cota porque no comparan elementos entre sí, sino que usan la estructura de las claves. Solo aplican a enteros o cadenas de longitud acotada.

TABLA COMPARATIVA FINAL

• Burbuja, selección, inserción — O(n²), in situ; inserción es estable y adaptable.
• Merge — O(n log n) garantizado, estable, O(n) extra.
• Quick — O(n log n) promedio, in situ, el más rápido en la práctica.
• Heap — O(n log n) garantizado, in situ, no estable.

LO QUE TE LLEVAS DEL CURSO

Ninguna estructura es la mejor: cada una intercambia tiempo por espacio, y velocidad de una operación por velocidad de otra. Lo que este curso entrena es reconocer qué operación va a dominar en tu problema y elegir en consecuencia. Esa es la habilidad que se transfiere a bases de datos, a sistemas operativos y a cualquier programa que maneje volumen.

EVALUACIÓN

40% actividades y ejercicios, 15% cada parcial y 15% el examen final, según la planeación oficial.