INDICE

ÍNDICE

Introducción 1
Estructura de los programas de la práctica 2
Estructura de datos 4
Operaciones sobre la estructura de datos 6
Cargar y guardar datos (discomemoria) 9
Implementación dealgoritmos de clasificación 10
Estudio del coste promedio de la comparación de cadenas de caracteres 20
Estudio teórico del tiempo de ejecución del algoritmo de Selección 21
Estudio teórico deltiempo de ejecución del algoritmo de Burbuja 22
Estudio teórico del tiempo de ejecución del algoritmo de Inserción 24
Estudio teórico del tiempo de ejecución del algoritmo de MergeSort 26
Estudioteórico del tiempo de ejecución del algoritmo de QuickSort 29
Estudio teórico del tiempo de ejecución de los algoritmos de MergeSort y QuickSort con caso base variable 33
Cuadro resumen de los tiempos deejecución de los algoritmos de clasificación 35
Mejora: Ordenación por Mezcla (MergeSort) no recursivo 36
Mejora: Ordenación Rápida (QuickSort) no recursiva 37
Mejora: Optimización en el caso másdesfavorable de QuickSort 38
Programa de implementación de los algoritmos de clasificación: MENU 39
Programa generador de ficheros aleatorios: GENERADOR 40
Validación de los algoritmos: COMPARA 41Estudio experimental: TIEMPO y ANALISIS 42
Estudio experimental: Introducción 43
Estudio experimental: Estructura de los resultados experimentales 44
Comentarios y observaciones sobre el primerestudio: Análisis de todos los algoritmos de clasificación 48
Comentarios y observaciones sobre el segundo estudio: QuickSort y MergeSort con caso base variable 50
Estudio primero: Análisis de todoslos algoritmos de clasificación 52
Caso 1. Fichero de tamaño grande y orden aleatorio 52
Caso 2. Fichero de tamaño grande y ordenado creciente 55
Caso 3. Fichero de tamaño grande y ordenadodecreciente 58
Caso 4. Fichero de tamaño medio y orden aleatorio 61
Caso 5. Fichero de tamaño medio y ordenado creciente 63
Caso 6. Fichero de tamaño medio y ordenado decreciente 65
Caso 7....