Primer Taller de Investigación

Presentamos nuestro taller de investigación de Algoritmos y Estructuras de Datos II.
Desarrollaremos el tema de comparación de métodos de ordenación directa y logarítmica.

Para esto utilizaremos algoritmos de ordenamiento, los cuales insertan elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida debe ser una permutación o reordenamiento de los datos de entrada. 

Funcionamiento del algoritmo para el taller

El algoritmo al ejecutarse le solicita al usuario que ingrese la cantidad de elementos que desea que tenga el arreglo. Luego muestra al usuario 2 opciones para elegir si desea ingresar manualmente los elementos o generarlos aleatoriamente y luego otro menú para elegir con que método ordenarlo. Posterior a esto, imprime por pantalla el arreglo original, el arreglo ordenado y la cantidad de pasadas, intercambios, comparaciones que realizó el método que elegimos previamente, así como también el tiempo de ejecución del algoritmo

El código vuelve al menú principal y brinda la posibilidad de probar todos los métodos en el mismo o ingresar un nuevo arreglo. Para salir del código se ingresa 0.

Enlace al código C
Enlace al código TAD (Librería utilizada)

Los diferentes métodos de ordenación que optamos para desarrollar y comparar son:

Métodos directos:

• Ordenación por intercambio directo (Burbuja).
• Ordenación por selección (Obtención sucesiva de menores).
• Ordenación por inserción directa (Baraja).

Métodos logarítmicos:

•     Método de Shell (Inserción con  incrementos decrecientes).
•     Método de QuickSort (Clasificación rápida).

Ordenación por intercambio directo (Burbuja):

La Ordenación de burbuja es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

En forma genérica, podemos observar que si se efectúan n-1 pasadas y a su vez cada pasada requiere n-1 comparaciones, la ordenación total exigirá:

La cantidad de intercambios dependerá del grado de desorden en que estén los datos.

El tiempo necesario para su ejecución es proporcional a n^2.

Es fácil implementar y no requiere memoria adicional, pero es muy lento y uno de los métodos más pobres en rendimiento.

Ordenación por selección (Obtención sucesiva de menores):

Este método consiste en buscar o seleccionar el menor elemento del arreglo y colocarlo en la primera posición. Luego se busca el segundo elemento más pequeño y se lo ubica en la segunda posición y así sucesivamente hasta llegar al último elemento. Este mecanismo se basa en obtener los menores y ubicarlos en la posición ideal.

Una gran desventaja de este método es que se realizan n-1 recorridos, lo cual nos obliga a recorrer la lista un número fijo de veces, sin detectar si está ordenada en alguno de los recorridos.

Al igual que el ordenamiento burbuja, el número de comparaciones entre elementos es independiente de la disposición inicial de los mismos.

En el primer recorrido se realizan n-1 comparaciones, en el segundo n-2 comparaciones y así sucesivamente hasta llegar al último recorrido en el cual se realiza 1 comparación.

La cantidad total de comparaciones se expresa con: n*(n-1)/2

El total de intercambios será n-1, ya que se realiza intercambio de un elemento consigo mismo.

Ordenación por inserción directa (Baraja):

Este método es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria.

Consiste en insertar un elemento en el vector en una parte ya ordenada de este vector y comenzar de nuevo con los elementos restantes.

El método de inserción directa es el que generalmente utilizan los jugadores de cartas cuando las ordenan, provocando que se conozca con el nombre del método de la baraja. La idea central consiste en insertar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-esimo elemento.

Si el elemento a insertar es mayor que los elementos restantes, el algoritmo realiza solo una comparación; si es menor a los elementos restantes, el algoritmo ejecuta n-1 comparaciones. Por lo tanto el número de comparaciones en promedio será la mitad de dicho número.

Según el orden en que estén los elementos dentro del vector:

-Si los elementos están ordenados completamente realizamos (n-1) comparaciones como mínimo.

-Si los elementos están en orden inverso tenemos un máximo de n(n-1)/2 = (n2-n)/2

-Si los elementos aparecen en el arreglo de forma aleatoria, el número de comparaciones se calcula sobre la base del promedio, que no es más que la suma de las comparaciones mínimas y máximas dividido 2.

Comparaciones promedio = (n2+n-2)/4

Método de Shell (Inserción con  incrementos decrecientes):

Es una versión mejorada del método de inserción directa. Cada elemento se compara, para su ubicación correcta en el vector, con los elementos que se encuentran en la parte izquierda del mismo. Si el elemento a insertar es mas pequeño que el grupo de elementos que se encuentran a la izquierda, es necesario efectuar varias comparaciones antes de su ubicación. Las comparaciones entre los elementos no son consecutivas, sino que están separados por una serie de posiciones (salto) de mayor tamaño pero con incrementos decrecientes, de esta manera los elementos quedan ordenados en el arreglo más rápidamente.

Primero se determina el salto entre los elementos a comparar. Es la parte entera de sumar 1 a la longitud del arreglo, y dividirlo entre 2.

Se recorre comparando el primer elemento con el que está situado “S” posiciones más adelante. Si los elementos comparados están en orden incorrecto, se intercambian; caso contrario quedan donde están. Luego se comparan los 2 elementos siguientes y así sucesivamente.

Este proceso se repite hasta que uno de los elementos de la comparación sea situado en la última posición del arreglo. Si durante la pasada hubo algún intercambio, se vuelve a repetir el proceso con el mismo salto hasta que no se produzcan intercambios.

Luego se modifica el salto: será la parte entera del resultado de sumar  1 al salto anterior, y dividirlo entre 2. El proceso finaliza cuando, siendo el salto igual a 1, se haya realizado una pasada sin intercambios.

Método de QuickSort (Clasificación rápida):

Este método es una optimización del método de intercambio directo y su autor C.A. Hoare lo llamó Quicksort (ordenación rápida) por la velocidad con que ordena los elementos de un arreglo.

Actualmente es uno de los más eficientes y veloces de los métodos de ordenación interna, y se basa en el hecho de que es más fácil ordenar dos listas pequeñas que una lista grande.

El tiempo de ejecución promedio es proporcional a (n* log n) y en el peor de los casos el tiempo de ejecución es proporcional  n^2.

La idea central consiste en:

-Tomar un elemento X que va a ser el pivote (valor elegido en forma arbitraria).

-Tratar de ubicarlo en la posición correcta del arreglo, de forma tal que todos los elementos que se encuentren a su izquierda sean menores o iguales a X y que todos los elementos que se encuentren a su derecha sean mayores o iguales a X.

-El algoritmo termina cuando todos los elementos se encuentran en su posición correcta en el arreglo.

El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).  Para realizar una versión iterativa se utiliza una pila en que se van guardando los límites superior e inferior de cada sublista.

Si se posee un arreglo con una gran cantidad de elementos, o que estén muy desordenados, QuickSort va a ser más indicado de usar que el resto de métodos.

Experiencia  y Conclusiones.

La experiencia grupal del tema desarrollado fue muy grata ya que aprendimos como se implementan los diferentes métodos de ordenamiento, su funcionamiento y aplicaciones en la vida cotidiana.

Al principio, nos reunimos para aprender la metodología del tema que íbamos a trabajar e hicimos una puesta en común del mismo. Le asignamos a cada integrante la realización de una tarea, como diseñar los códigos en C y en TAD, explicar qué realiza cada uno, la búsqueda de información en libros e internet, etc.

Una fortaleza del grupo fue que cada integrante estaba dispuesto a aprender sobre el tema y diseñar una solución mediante la aprehensión de métodos y así obtener un resultado concreto.

Algunas desventajas fueron la falta de experiencia del grupo y la falta de tiempo para reunirnos todos los integrantes. Pero igualmente logramos llevar a cabo una distribución de tareas y una puesta en común de las mismas, para que cada integrante exprese su opinión y aporte mejoras e ideas al diseño del código, entre ellas: la duración, optimización, rendimiento, reusabilidad, velocidad, etc.

Luego realizamos la búsqueda en libros e Internet sobre el funcionamiento de cada método, aprendiendo su estructura, aplicación y pasos a seguir para obtener el resultado que deseamos.

Finalmente, con toda la información que obtuvimos, realizamos el código en C, y creamos un TAD para almacenar en él la declaración y el cuerpo de las funciones que contienen los distintos métodos, así como también las variables globales.

Implementamos menú iterativo para dar distintas opciones al usuario, siendo una manera más factible y organizada de elegir que método utilizar para ordenar el arreglo. Decidimos poner un límite al ingreso de valores para evitar fallas en el rendimiento del código. Al final se imprimen tanto el arreglo original como el ordenado, y la cantidad de pasadas, intercambios y comparaciones que realizo el método. Para poder calcular el tiempo de ejecución utilizamos la librería time.h, la cual contiene al tipo de dato clock_t con el que declaramos las variables inicio y final para usarlos como parámetros.

Llegamos a la conclusión de que podemos aplicar distintos métodos al ordenamiento de un arreglo, pero si tenemos que optar por uno de ellos, ya sea por su rapidez o porque no requiere memoria adicional, el método QuickSort sería el más adecuado de utilizar, ya que mientras más grande sea la dimensión del arreglo, existen más posibilidades de que este esté más desordenado, logrando una diferencia considerable con respecto al resto de métodos elegidos por el grupo.