La fecha de entrega es hasta el 30 de enero. Después de la entrega se fijará una fecha de revisión durante la semana siguiente. Se corregirá en C sobre Linux en las salas de prácticas (sala 1.5).

Para trabajar en la sala de prácticas cada alumno deberá pedir una cuenta al profesor correspondiente: Joaquín Cervera para Gestión, y Domingo Giménez para Sistemas..

Debe entregarse la documentación sin incluir los programas.

En la portada de la documentación debe figurar: nombre del alumno, número de práctica, Sistemas o Gestión, cuenta, password y directorio donde están instalados los programas (de manera que se facilite el proceso de corrección de la práctica).

La documentación debe contener un apartado (conciso y claro) por cada uno de los apartados del enunciado. Los apartados en la documentación deben numerarse e ir en el mismo orden que en este documento, en caso contrario pueden no ser evaluados. 

Se estudiarán distintos métodos de ordenación por comparación: al menos tres métodos directos elegidos por el alumno (inserción, selección, burbuja, sacudida, ...) y los métodos divide y vencerás mergesort y quicksort vistos en clase con tamaño del caso base variable, pudiendo usarse como solución para el caso base cualquiera de los métodos directos anteriores.

Los datos a ordenar serán cadenas de caracteres, que se tomarán de un fichero ASCII que contendrá una cadena por línea. La salida será un fichero del mismo tipo que el de entrada con las cadenas ordenadas en orden alfabético.

El estudio debe contener todos y cada uno de los siguientes puntos:

1) Estudios previos:

1.a) (0.5 puntos) Se explicarán los detalles de implementación: estructura utilizada para almacenar los datos, función de comparación y de asignación utilizada o programada, funciones del esquema divide y vencerás, ... 

1.b) (0.5 puntos) Estudio del coste promedio de la comparación de cadenas de caracteres.

1.c) (1 punto) Se estudiarán teóricamente los tiempos de ejecución de todos los métodos considerados. El estudio debe comprender la identificación de los casos más favorable y más desfavorable, y el estudio de estos casos y del promedio. En todos los casos se estudiarán las notaciones asintóticas. El estudio se hará en función del número de cadenas a ordenar y considerando que el contenido de las cadenas es aleatorio. En los métodos divide y vencerás se considerará tamaño del caso base uno.

1.d) (0.75 punto) De forma similar al apartado anterior se estudiarán teóricamente los métodos divide y vencerás con tamaño del caso base variable, y se estudiará teóricamente el tamaño óptimo del caso base. De este estudio y del realizado en los apartados 1.b) y 1.c) sobre los métodos directos, ¿se puede decidir qué tamaño de caso base parece más apropiado y qué método directo parece más apropiado usar para ese caso base?

2) Posibles optimizaciones:

Se considerarán posibles optimizaciones sobre los métodos divide y vencerás estudiados en clase:

2.a) (0.5 puntos) En la ordenación por mezcla se estudiará la posibilidad de evitar copias de datos utilizando una estructura auxiliar de manera que en un paso se mezclen datos de la estructura origen a la auxiliar y en el siguiente paso de la estructura auxiliar a la origen.

2.b) (0.5 puntos) Se estudiará cómo evitar la recursión en el esquema de ordenación por mezcla. 

2.c) (0.5 puntos) La ordenación rápida tiene un caso más desfavorable de coste cuadrático. Para evitar este caso más desfavorable se puede elegir el pivote tomando una muestra pequeña de los datos, ordenándola y utilizando el elemento central de la muestra ordenada como pivote. 

2.d) (0.5 puntos) Se estudiará cómo evitar la recursión en el esquema de ordenación rápida. 

2.e) Cualquier otra mejora propuesta para estos métodos se valorará positivamente.

3) (2.5 puntos) Implementaciones:

Se programará una función de ordenación por cada uno de los métodos del apartado 1 y cada una de las optimizaciones del apartado 2, con parámetro de entrada la estructura donde se almacenen los datos leídos del fichero, y con parámetro de salida en la que se guardan los datos antes de escribirlos en un fichero. En los métodos por divide y vencerás un parámetro será el tamaño del caso base.

No hay que incluir en la documentación los códigos de los programas.

Se valorará la facilidad y la generalidad (no restringir a una cantidad limitada de cadenas ni a cadenas de longitud limitada, ...) de las funciones.

Aunque este apartado tiene un valor de 2.5 sobre diez en la valoración final de la práctica, será condición necesaria para aprobar la práctica el que las funciones programadas funcionen correctamente.

4) Validación de los programas:

Para validar los programas hay que hacer una serie de pruebas. Para esto habrá que hacer:

4.a) (0.5 punto) Se hará un programa para permitir realizar las comparaciones que se crea oportunas entre los distintos métodos, por ejemplo, pidiendo el fichero de entrada y los dos métodos que se quiere comparar, y programando una función que nos compare los resultados obtenidos con los dos métodos.

4.b) (0.25 puntos) El alumno explicará las pruebas que ha realizado para estar convencido de que sus funciones trabajan correctamente.

5) Estudio experimental:

5.a) (1 punto) Para estudiar experimentalmente los distintos métodos se realizará un programa para obtener tiempos de ejecución (se puede usar la función gettimeofday) de los distintos métodos implementados, variando el tamaño de la entrada, y del caso base en los métodos divide y vencerás, y pudiendo variar el método directo a utilizar en el caso base, generando las entradas de manera aleatoria y en los casos más favorable y más desfavorable. Se obtendrán resultados experimentales para valores significativos (los que son valores significativos lo tiene que decidir y justificar el alumno) y se compararán los distintos métodos en los diferentes casos analizados.

5.b) (1 punto) Se contrastarán los resultados teóricos y los experimentales, comprobando si los experimentales confirman los teóricos, para los resultados teóricos obtenidos en el apartado 1). El alumno justificará los experimentos realizados para contrastarlos con la teoría, y en caso de discrepancia entre la teoría y los experimentos debe intentar buscar una explicación. En particular hay que confirmar la forma en que crecen los tiempos de ejecución, qué método es mejor para una determinada entrada, si las mejoras teóricas lo son en la práctica, si el tamaño óptimo del caso base es el obtenido teóricamente, si el método directo a utilizar en el caso base es el predicho teóricamente, ...