Estructura de Datos y Algoritmos
1er. Sem 2004
Tarea 2: HeapSort y QuickSort
El objetivo de esta tarea es
estudiar la distribución del costo de dos algoritmos de
ordenamiento. Al mismo tiempo el estudiante aprenderá
cómo mostrar un resultado en forma gráfica.
Desarrolle el programa
>$ histograma <número_de_repeticiones>
<tamaño_conjunto_datos>
El histograma luego de ser
ejecutado muestra una gráfica con dos histogramas de frecuencia
de tiempo. Cada historgrama representa la frecuencia del tiempo
tomado en ordenar un conjunto de enteros de tamaño dado por el
segundo argumento del programa. El primer argumento indica el
número de conjuntos ordenados.
Su tarea debe ser estructurada en los siguientes archivos. Use los
mismos nombres.
heapSort.c : Contiene el
algoritmo de ordenamiento heapsort para un
arreglo de enteros. A la función de ordenamiento
simplemente nombrela heapSort(..).
Adicionalmente en este archivo ponga las otras funcniones de apoyo para
implementar este algortimo.
quickSort.c : Contiene el
algoritmo de ordenamiento quicksort. A la función de
ordenamiento simplemente
nombrela quickSort(...).
histograma.c : Contiene
la función main que, para cada algoritmo, crea tantas
repeticiones para medir el tiempo de ejecución del algoritmo de
ordenamiento como lo indica el primer argumento. Cada arreglo posee
datos aleatorios y su tamaño se indica en el segundo argumento
del
programa.
La corrección de su tarea se hará en aragorn.elo.utfsm.cl
Ayuda:
- Para ambos algoritmos de ordenamiento usted puede encontrar una
implementación en C en el texto "Algorithms
in C" de Robert Sedgewick, el cual viene con un archivo con todos
los algoritmos del texto
codificados en C.
- También puede encontrar implementaciones en las tareas
entregadas por sus compañeros en años anteriores.
- Para generar los datos a graficar se sugiere almacenar en un
arreglo el tiempo tomado en cada repetición. Luego subdividir el
rango en tantos intervalos o clases según 1+3.3*log10(n),
donde n es el número de repeticiones. En otro arreglo almacene
para
cada intervalo la cantidad de mediciones dentro del intervalo.
Éste contiene los datos del histograma de frecuencia. Escriba el
valor medio de cada intervalo y la frecuencis de datos de éste
en un archivo temporal.
- Para graficar sus resultados se sugiere crear un archivo de
comando para gnuplot
el cual tomará los datos del archivo y los
mostrará en pantalla.
- Estudie el comando la función system(..) de C.
- Nuevas secciones de ayuda se incluirán en la medida que
hayan
consultas.