primera clase

Este primer trabajo consiste en realizar un experimento con el objeto de determinar qupe método de ordenamiento es "mejor", en qué caso lo es y porqué.

No olviden bajar el material de la intranet del instituto.

Acá va el ejercicio:

Probar diferentes algoritmos de ordenamiento

Consigna

El objetivo de este proyecto es realizar comparaciones entre distintos métodos de búsqueda y de ordenamiento en vectores.

Desarrollar las siguientes funciones de búsqueda:
a) búsqueda en un vector desordenado;
b) búsqueda en un vector ordenado;
c) búsqueda binaria en un vector ordenado;

Para cada caso es importante contar cuántas comparaciones se realizaron, y devolver este valor, además de la ubicación del valor si fue encontrado o -1 en caso que no se haya encontrado.

Comparar diferentes métodos de búsqueda es realizar muchas búsquedas de los mismos valores, con cada uno de los métodos, contar la cantidad de comparaciones y obtener el promedio en cada caso. Para poder comparar los distintos métodos de búsqueda prepare un lote de prueba (valores a buscar en el arreglo), y procese cada valor del lote de prueba utilizando cada método.

Desarrollar las siguientes funciones de ordenamiento:
a) burbujeo;
b) de a pares;
c) shell;
d) cualquier otro que usted proponga.
Para cada caso es importante contar cuántas comparaciones y cuántos cambios se realizaron, devolviendo estos valores, junto con el vector ordenado.

Comparar diferentes métodos de ordenamiento es procesar el mismo vector con cada uno de los métodos, contar la cantidad de comparaciones y cambios y obtener el promedio en cada caso.

Para poder implementar este proyecto se debe crear un menú que permita probar cada uno de los métodos de búsqueda y de ordenamiento desarrollados.

Para que las comparaciones tengan sentido y podamos obtener resultados razonables, el vector en el que se busca y/o el que se ordena debe ser grande, digamos 10.000 elementos. Para generar los valores que llenarán un vector de esa magnitud debemos utilizar la función random del lenguaje C++ (buscar en el help la sintaxis de randomize() y de random(nnn)).

Para comparar métodos de búsqueda debemos buscar muchos valores, por ejemplo 100, para lo cual también se debe implementar una generación random de 100 números (en un vector), y realizar la búsqueda a través de los distintos métodos con dichos valores. También puede grabar en un archivo, y luego leerlos del mismo para llenar los vectores los vectores.

Entonces el menú debe contener además de los métodos de ordenamiento y búsqueda otras cuatro opciones:
a) generar números para el vector de búsqueda y ordenamiento.
b) generar números para buscar.
c) guardar en archivos el vector de búsqueda y ordenamiento (a), y el de números para buscar (b).
d) leer desde el archivo de búsqueda y ordenamiento y armar el vector para tal fin, y desde el archivo de números para buscar y armar el vector correspondiente.

También es importante poder ver el contenido del vector; por lo tanto debemos tener una función que nos permita ver el vector, y dos entradas en el menú, para ver el vector de búsqueda, y ordenamiento y el de los números a buscar.

Por último es importante poder modificar algunos números del vector de búsqueda y ordenamiento, y del vector de números para buscar, así que se debe escribir una función a tal fin y dos entradas en el menú, una para cada caso. Esta técnica permite fijar determinados valores en determinados lugares, y así poder analizar más “finamente” qué sucede con cada uno de los métodos de ordenamiento. Evalúe forzar los valores mayores al inicio del vector, y verifique la cantidad de cambios y comparaciones, luego que los valores mayores estén hacia el final y repita el experimento, luego haga lo mismo fijando los valores mayores hacia el centro del arreglo y repita las operaciones. Por último analice los resultados de las cuatro pruebas (recuerde que la primera fue con los valores distribuidos al azar). Es importante también contabilizar el tiempo de ejecución, el cual se puede hacer con un simple reloj, o utilizando las funciones de tiempo que están en la librería (en la misma que están las funciones random).

Finalmente debemos escribir, y agregar al menú una función que muestre en pantalla todos los resultados (recordar que son valores que nos van a permitir realizar comparaciones entre los diferentes métodos), y grabar dichos valores en un archivo de resultados.

El proyecto debe incluir conclusiones referidas a explicar qué pasa con los distintos métodos, cuál es mejor, y si esto depende del tamaño del vector, qué pasa si el vector a ordenar está más o menos ordenado al inicio del proceso, y cómo influye esto en la elección del método.

Responder:

¿Cuál método funcionó mejor en cada uno de los casos?
¿Qué diferencias encontró entre lotes de datos ordenados y desordenados?
¿Cuáles considera mejores o peores según la cantidad de orden o azar imperante en los grupos de datos?

Pueden consultar en Internet acerca de diferentes métodos de ordenamiento.

Algunos sitios recomendables:

Métodos de Ordenamiento. Tipos de ordenamiento y medidas de eficiencia. Algoritmos básicos. QuickSort. HeapSort. BinSort. RadixSort. Arboles de Decisión ...DEPARTAMENTO DE COMPUTACIÓN CINVESTAV México

Les sugerimos utilzar el biscador Google para encontrar diferentes "metodos de ordenamiento".

Daniel
Marcelo