ELO 320 1er. Sem. 2002
1º Tarea de Programación: Insertion sort, Mergesort y Heapsort.
Objetivos:
Aplicar uso de "makefile" para la compilación de progrmas.
Desarrollo de programas modulares y el manejo de proyectos de archivos multiples
Conocer y aplicar integracción y comunicación con módulos
externos, en particular gnuplot.
Medición de tiempos en procesos no deterministicos.
Programación de algoritmos de ordenamiento.
Obtener tiempos de ejecución de algoritmos de ordenamiento.
Actividad:
Haga un programa que muestre un gráfico de valores
medios y un diagrama de la evolución dimámica del los algoritmos.
Valores medio: En un solo gráfico muestre los valores promedios para
ordenar N datos con N= 50..5000. Para cada punto tome el promedio de 10 resultados
(para el mismo N). En el gráfico identifique claramente cara curva.
Diagrama: Para cada algoritmo haga un diagrama de puntos (i, A[i]) i= 0..M-1
y donde los valores del arreglo son inicialmente números aleatorios
tomados en el rango 0..(M-1). M es un parámetro del programa. Haga
un diagrama al comenzar el algoritmo, luego otro despues de más o
menos en la mitad del algoritmo (usted defina esto más precisamente),
y luego otro al final.
A Entregar:
Un archivo con implementación del algoritmo Insertion Sort.
Un archivo con implementación del algoritmo Mergesort.
Un archivo con implementación del algoritmo Heapsort.
Un programa que use los tres de arriba para resolver el gráfico pedido.
Un programa que use los tres de arriba para resolver el diagrama pedido.
Si usted lo estima necesario, separe el problema en más archivos aún.
Un archivo makefile.
Un archivo Readme.
Revisar el procedimiento de evaluación antes de entregar la tarea.
Ver : gettimeofday(), gnuplot, rand(), fprintf(). También hay
implementaciones de estos algoritmos en C
e implementaciones en C++
. Buscar por insertion, mergesort y heapsort en estos archivos.Pueden encontrar
implementaciones de los algoritmos en C