Estructura de Datos y Algoritmos
1er. Sem 2004
Tarea 1: Insertion and Merge Sort

El objetivo de esta tarea es adquirir comocimiento con el ambiente de programación del Departamento de Electrónica y la programación de dos algorimos de ordenamiento.

Desarrolle dos programas:
    timeInsertionSort <tamaño_de_ arreglo>
    timeMergeSort <tamaño_de_arreglo>

Ambos programas arrojan por pantalla el tiempo tomado para ordenar un arreglo de enteros de tamaño dado por el argumento del programa y la desviación estándar para este tiempo. Este tiempo de ordenamiento es el resultado de promediar 10 veces la tarea de ordenar el arreglo con dintintos valores. En timeInsertionSort el algoritmo usado para ordenar es insertionSort visto en clases. En timeMergeSort el programa usa el algoritmo mergeSort.

Su tarea debe ser estructurada en los siguientes archivos. Use los mismos nombres.

insertionSort.c  : Contiene el algoritmo de inserción para ordenar arreglos de enteros. A la función de ordenamiento simplemente nombrelas ordenar().
mergeSort.c : Contiene el algoritmo recursivo mergeSort y el algoritmo de mezcla merge. A la función de ordenamiento simplemente nombrelas ordenar().
main.c  : Contiene la función main que crea el arreglo e invoca 10 veces a la función ordenar() [ OJO hay dos implementaciones de esta función, una en insertionSort() y otra en MergeSort() ]con distinto contenido para obtener el promedio del tiempo. Termina mostrando por pantalla el tiempo promedio y la desviación estándar.
makefile  : contiene las reglas para compilar los archivos fuentes y genera los dos ejecutables pedidos.

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.
• Para medir tiempo, estudiar el uso de la función gettimeofday(), malloc().
• dato para el cálculo de promedio y varianza.
  
  Se recomienda manejar dos variables auxiliares sum_xi y sum_xi2 con lo cual resulta muy simple ontener m y s al término de las iteraciones.
  
• Estudiar qué hace el comando tar -cvzf  dir/
• Estudiar qué hace el comando ssh su_cuenta@aragorn.elo.utfsm.cl -X
  
• Estudiar las notas sobre creación de makefiles y preprocesador C.
  
• Nuevas secciones de ayuda se incluiran en la medida que hayan consultas.