GUÍA 02-09-26 Estructuras de Datos

CN122 · miércoles 02/09/2026 · 13:00-14:15 · Sesión 8

Ejercicios con registros · Ordenamiento por clave

SESIÓN DE TALLER

Se consolida lo de arreglos y registros resolviendo problemas completos, no fragmentos.

ORDENAR POR UN CAMPO

Ordenar registros es igual que ordenar números, con dos diferencias: la comparación se hace sobre un campo y el intercambio mueve el registro completo.

• Comparar cadenas requiere strcmp, nunca ==. El operador == compara direcciones.
• Si el registro es grande, ordenar un arreglo de apuntadores o de índices evita copiar estructuras completas.

ORDENAMIENTO INDIRECTO

Se ordena un arreglo de índices según el criterio, dejando los datos quietos. Permite tener varios órdenes simultáneos —por matrícula y por promedio— sin duplicar la información. Es lo que hace un índice de base de datos.

BÚSQUEDA BINARIA

1. Requiere que el arreglo esté ordenado por la clave de búsqueda.

2. Se compara con el elemento medio y se descarta la mitad.

3. Costo O(log n) frente a O(n) de la secuencial.

4. Cuidado con el cálculo del medio: usar ini + (fin−ini)/2 evita desbordamiento.

CUÁNDO CONVIENE ORDENAR PARA BUSCAR

Ordenar cuesta O(n log n). Si vas a hacer una sola búsqueda, la secuencial es más barata. Si vas a hacer muchas, ordenar una vez se amortiza. Ese razonamiento sobre el costo total, y no sobre la operación aislada, es el que se espera en el curso.

PRÁCTICA

Ordenar el arreglo de registros por dos criterios distintos y comparar búsqueda secuencial contra binaria midiendo comparaciones.