Objetivos

El objetivo de esta tarea es realizar una pequeña investigación experimental basada en tres algoritmos de ordenación de costo cuadrático.

Utilizar algoritmos iterativos.

Para realizar la implementación de los algoritmos se debe utilizar el lenguaje Java (disponible en las estaciones de trabajo del DCC y del CEC). No se permite el empleo de otro lenguaje.

Descripción de la tarea

Deben analizar e implementar tres métodos de ordenación sencillos:
 
• Inserción
• Selección
• Burbuja


Los métodos de ordenación deben generar conjuntos ordenados de menor a mayor.

La característica que se va a medir es contar el número de comparaciones entre pares de elementos del conjunto a ordenar, por lo cual tienen que contemplar este requerimiento en la implementación de los algoritmos de ordenación.

Luego tienen que realizar tres tipos de pruebas de ordenación:
 

1. Un conjunto con elementos generados aleatoriamente (que por supuesto es un conjunto desordenado).
2. El conjunto resultante de la prueba 1, con elementos ordenados de menor a mayor.
3. El conjunto resultante de la prueba 1, con los elementos ordenados de mayor a menor.


Variando el tamaño de los conjuntos para cada tipo de prueba, consideren conjuntos de tamaño 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000 y 10000 elementos. Consideren elementos enteros en el rango [0, 100000].

Deben tener en cuenta que cuando generan elementos aleatorios, puede ocurrir que tengan elementos repetidos, luego tienen que adecuar el algoritmo para soportar el caso que se repitan elementos de modo de minimizar las comparaciones.

El programa debe generar tres archivos de texto (insercion.txt, seleccion.txt y burbuja.txt) donde se muestren los resultados obtenidos según el siguiente formato:

<nombreAlgoritmo>    <numElem>    <numCompAleatorio>    <numCompMenorMayor>    <numCompMayorMenor>

Ejemplo:

insercion.txt
insercion    1000    <numCompAleatorio>    <numCompMenorMayor>    <numCompMayorMenor>
insercion    2000    <numCompAleatorio>    <numCompMenorMayor>    <numCompMayorMenor>
...
insercion    10000    <numCompAleatorio>    <numCompMenorMayor>    <numCompMayorMenor>

En el informe tienen que presentar en tres tablas (generados aleatoriamente, de menor a mayor, de mayor a menor) los resultados obtenidos en las pruebas, y adjuntar un gráfico asociado a cada tabla. De este modo podrán comparar los tres algoritmos para cada tipo de prueba.

Por último deben realizar el ajuste polinomial que corresponda a cada prueba para cada algoritmo (son 9 ajustes en total), y deben entregar una pequeña conclusión sobre qué algoritmo es mejor para cada caso (generados aleatoriamente, de menor a mayor y de mayor a menor).

Restricciones

• El programa debe ser escrito en Java. No se acepta ningún otro lenguaje de programación.
• Plazo de entrega: 2 semana desde la fecha de publicación (vean el encabezado). No se recibirán tareas atrasadas.
• Queda prohibido utilizar bibliotecas o clases preconstruidas en el lenguaje que implementen:
• Listas, o arreglos (por ejemplo NO use la clase List y sus derivadas, y NO use la clase Arrays y sus derivadas).
• Algoritmos de ordenación solicitados.
• La tarea es individual.
• Tienen que respetar los nombres de los archivos y los formatos de estos según las indicaciones entregadas en el enunciado. Se evaluará el cumplimiento de esta norma
• Para la generación de elementos aleatorios pueden utilizar el método Math.random(), o un objeto de la clase Random (mayor referencia en la API de java). Se recomienda el uso de la clase Random.
• Para la tarea tienen que entregar un informe de resultados junto al código fuente (el programa que implementa la tarea). No se aceptan códigos si informe ni informes sin código.
• Cualquier falta a las restricciones anteriores invalida irrevocablemente la tarea. Revisen las normas descritas en el plan del curso

Pruebas y Resultados

Las indicadas en la descripción de la tarea.

Ponderación

El informe equivale a un 50% de la nota de tarea.
El código equivale a un 50% de la nota de tarea.

Entrega de la tarea
 

La entrega de la tarea debe incluir un informe escrito donde se describa y documente el programa realizado, y se incluyan ejemplos de entradas y salidas.

El informe debe ser entregado en la Secretaría Docente de Computación (donde Magaly, segundo piso torre central, hasta las 17:00 horas del último día de plazo), y el código fuente (junto a un archivo README que explique como compilar) debe ser enviado utilizando el Cursomático de cc30a.

El contenido del informe debe seguir la siguiente pauta común para todas las tareas:
 

Portada

Universidad de Chile
Facultad de Ciencias Físicas y Matemáticas
Departamento de Ciencias de la Computación
Informe Tarea X

Nombre de la tarea X

 

	Fecha:	fecha entrega
	Autor:	nombre alumno
	E-mail:	correo del alumno

• Introducción: Descripción del problema y de su solución
• Análisis del Problema: Se expone en detalle el problema, los supuestos que se van a ocupar, las situaciones de borde, y la metodología para abordar el problema.
• Solución del problema:
• Algoritmo de solución: Se detallan los pasos a seguir para solucionar el problema. De ser necesario, se recomienda incluir figuras, tablas, etc., que permitan mejorar la comprensión del problema.
• Diagrama de Estados: Muestra en forma global el programa.
• Diseño: Explicitar las Pre y Post condiciones consideradas, mostrar los invariantes empleados.
• Implementación: Se debe mostrar el código del programa que soluciona el problema (omita los detalles que no tengan relevancia para el problema), explicando lo que hace el código. Se recomienda usar nombres representativos a las variables. NOTA: El código generado para resolver la tarea debe corresponder al diseño descrito, preocúpese de realizar los comentarios que sean necesarios.
• Modo de uso: Se debe explicar el modo de uso del programa y el modo de compilación. Nota: la tarea debe ser compilable en cipres o en los computadores del zócalo. Si las indicaciones que Usted entrega son erróneas al momento de compilar, la evaluación de su tarea será severamente penalizada.
• Resultados: En esta sección se deben indicar las pruebas realizadas y sus resultados. Se debe señalar claramente cuál es la llamada al programa y su salida.  En esta sección debe incluir las tablas y gráficos necesarios solicitados, y el análisis de los resultados. En este capítulo adjunten las conclusiones obtenidas de los resultados de la tarea.
• Anexos:
• Listados: Se debe incluir un listado con el programa completo que se compiló realmente (utilicen una fuente pequeña (8 pt) en este listado).
• Otros: De ser necesario, cualquier información adicional se debe agregar en los anexos y debe ser referenciada en alguna sección del informe de la tarea.