Busqueda qucksort+biharia hash con manejo de colisiones

Proyecto Final

“QuickSort + Binario, basado en vectores y

Hash con manejo de colisiones mediante Quadratic Proofing”

Mauricio Giraldo Valencia 2070694

Juan Pablo Moreno Villa 2070207

Informe presentado al Ing.:

Hernando González U.

Análisis de Algoritmos

Universidad Autónoma de Occidente

Santiago de Cali

Mayo 11 de 2009

Descripción

Este proyecto consiste enla implementación en Java del método de ordenamiento Quicksort, y los métodos de búsqueda binaria y hash, teniendo en cuenta en esta última el manejo de colisiones mediante quadratic proofing.

En este documento se entrega el diseño final UML de la aplicación java, explicando el funcionamiento de cada clase funcional, y además ilustraciones explicadas de estructura y componentes de las clasesutilitarias (en este caso la GUI).

Desarrollo

Para este proyecto se trabajó con el siguiente diseño UML:

Descripción Del Funcionamiento De Las Clases

Clase principal (main)

[pic]

En esta clase se da inicio a la aplicación. Esta, está ligada a la clase (o clases) GUI (graphic user interface), en donde se produce el flujo de entrada y salida de datos según lo disponga el usuario.Clase para el manejo de datos externos (archivos)

[pic]

Esta clase tiene dos funciones muy importantes, como lo es la entrada y salida de datos desde medios externos, puesto que tiene un método de creación y escritura de archivos externos, y otro para leer los datos desde un archivo existente. Además de esto tiene un método get… el cual sirve para poder devolver al programa los datoscargados externamente, para su procesamiento en la aplicación.

Interfaces de ordenamiento y búsqueda.

[pic]

Esta interfaz, dicta el comportamiento del ordenamiento en este caso el quickSort que es un método sin retorno alguno que debe recibir como argumentos los extremos de le conjunto de datos que se desea ordenar.

[pic]

La interfaz de la búsqueda binaria, se impone un método en el cual,además del conjunto de datos definido en cada clase como atributo, necesitan el dato que se va a buscar.

[pic]

La interfaz de la búsqueda Hash, se establecen métodos para la creación de la clave de cada dato, el manejo de colisiones, la creación del arreglo de claves, la búsqueda, la inserción, y la eliminación.

Clase búsqueda Binaria.

[pic]

Esta clase implementa la interfazbúsqueda cuyo único meto es buscar, que recibe el dato q se quiere procesar, en esta clase, el vector es un atributo de la clase y se obtiene a través del constructor, para luego en el método de búsqueda binaria (implementado en buscar), se realice el proceso de búsqueda.

Clase búsqueda Hash.

En esta clase implementa los métodos de la interfaz de la búsqueda hash, y además de estos, también tieneunos métodos adicionales, en los cuales se evalúa si un número es primo o no le es, se calcula el siguiente primo, a partir de un número x (el doble del tamaño del conjunto de datos), y otros dos métodos para la re-creación de las claves hash después de una eliminación.

Clase ordenamiento QuickSort.

[pic]

Esta clase implementa el método ordenar de la interfaz ordenamiento, y se podría decirque es el método más sobresaliente de los pertenecientes a esta clase. Los atributos que tiene esta clase son el conjunto de datos a ordenar (un vector) y los extremos del mismo. Además de esto solo hay métodos de asignación y retorno de funcionamiento simple (setters y getters).

Clases utilitarias - Interfaz grafica de usuario

La aplicación java tiene dos ventanas de interfaz de usuario laprimera que es para seleccionar la entrada de los datos y la segunda para realizar los procesos de ordenamiento y búsquedas. Los códigos de las clases no se incluyen debido a que no hacen parte de la estructura de diseño de la aplicación.

1. Ingreso de datos

[pic]

En esta ventana el usuario debe seleccionar como desea ingresar el conjunto de datos de entrada, ya sea manualmente por...