Estructura de datos III Algoritmos de ordenamiento_byPerses.doc Página 5 de 33 Introducción. Uno de los problemas fundamentales en la ciencia de la computación es ordenar una lista de items. Existen una infinidad de métodos de ordenamiento, algunos son simples e intuitivos, como el bubble sort, y otros como son extremadamente complicados, pero producen los resultados mucho más rápido. En este trabajo se presentan los algoritmos de ordenamiento más comunes, entre los cuales están los siguientes: Bubble sort, Heap sort, Insertion sort, Merge sort, Quick sort, Selection sort y Shell sort. Los algoritmos de ordenamiento pueden ser divididos en dos clases de acuerdo a la complejidad de los mismos. La complejidad del algoritmo se denota según la notación Big-O. Por ejemplo, O(n) significa que el algoritmo tiene una complejidad lineal. En otras palabras, toma 10 veces más tiempo en operar un set de 100 datos que en hacerlo con un set de 10 items. Si la complejidad fuera O(n2) entonces tomaría 100 veces más tiempo en operar 100 items que en hacerlo con 10. Adicionalmente a la compejidad de los algoritmos, la velocidad de ejecución puede cambiar de acuerdo al tipo de dato a ordenar, es por ello que es conveniente comprar los algoritmos contra datos empíricos. Éstos datos empíricos se deben elaborar tomando la media de tiempo de ejecución en un conjunto de corridas y con datos del mismo tipo. En este trabajo se ejecutaron 10 veces cada algoritmo de ordenamiento con un set de 10000 datos de tipo entero de c++. Se realiza también una comprativa con otros tipos de datos como ser el long y el char para todos los algoritmos y luego se los compara entre cada uno de ellos. En el gráfico siguiente se puede ver el tiempo de ejecución del algoritmo en función de la cantidad de elementos, se puede observar que si los elementos a ordenar son pocos, menos de 1000 casi todos los tienen el mismo tiempo de respuesta, pero si la cantidad de datos aumenta los tiempos de respuesta van cambiando drásticamente entre cada uno de los ellos, y para una cantidad de datos de 8000 ya se puede determinar que el peor algoritmo es el bubble sort, mientras que el mejor es el Heap sort. 
Tiempo Tiempo Comparativa de algoritmos 400 350 300 250 200 150 100 50 0 -50 0 2000 4000 6000 8000 10000 Poly. ( Bubble) Poly. ( Insertion) Poly. ( Selection) Poly. ( Quick) Poly. ( Shell) Poly. ( Heap) Poly. ( Merge) Elementos Análisis de los algoritmos Bubble sort Este es el método más simple y antiguo para ordenar un conjunto de datos, es también el más lento. El algoritmo bubble sort tiene dos bucles for internos que recorren el vector comparando el elemento j-esimo-1 con el elemento con el j-esimo elemento y en caso de que este sea mayor hace un cambio de los elementos. Al tener dos bucles internos el comportamiento es en general O(n2), y en las mejores condiciones se comporta como O(n). Bubble sort 400 350 300 250 200 150 100 50 0 0 2000 4000 6000 8000 10000 Elementos Estructura de datos III Algoritmos de ordenamiento_byPerses.doc Página 6 de 33 
Estructura de datos III Algoritmos de ordenamiento_byPerses.doc Página 7 de 33 Como funciona Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados. Con el array anterior, {40,21,4,9,10,35}: Primera pasada: {21,40,4,9,10,35} {21,4,40,9,10,35} {21,4,9,40,10,35} {21,4,9,10,40,35} {21,4,9,10,35,40} <– <– <– <– <– Se Se Se Se Se cambia cambia cambia cambia cambia el el el el el 21 por el 40. 40 por el 4. 9 por el 40. 40 por el 10. 35 por el 40. Segunda pasada: {4,21,9,10,35,40} <– Se cambia el 21 por el 4. {4,9,21,10,35,40} <– Se cambia el 9 por el 21. {4,9,10,21,35,40} <– Se cambia el 21 por el 10. Ya están ordenados, pero para comprobarlo habría que acabar esta segunda comprobación y hacer una tercera. Código fuente void bubbleSort (int numbers[], int array_size) { int i, j, temp; for (i = (array_size – 1); i >= 0; i–){ for (j = 1; j <= i; j++){ if (numbers[j-1] > numbers[j]){ temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp; } } } } Selection sort Este algoritmo trabaja seleccionando el item más pequeño a ser ordenado que aún esta en la lista, y luego haciendo un intercambio con el elemento en la siguiente posición. La complejidad de este algoritmo es O(n2). 
Tiempo Selection sort 180 160 140 120 100 80 60 40 20 0 0 2000 4000 6000 8000 10000 Elementos Como funciona. Este método consiste en buscar el elemento más pequeño del array y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segudo lugar, y así sucesivamente hasta colocar el último elemento. Por ejemplo, si tenemos el array {40,21,4,9,10,35}, los pasos a seguir son: {4,21,40,9,10,35} <– Se coloca el 4, el más pequeño, en primera posición : se cambia el 4 por el 40. {4,9,40,21,10,35} <– Se coloca el 9, en segunda posición: se cambia el 9 por el 21. {4,9,10,21,40,35} <– Se coloca el 10, en tercera posición: se cambia el 10 por el 40. {4,9,10,21,40,35} <– Se coloca el 21, en tercera posición: ya está colocado. {4,9,10,21,35,40} <– Se coloca el 35, en tercera posición: se cambia el 35 por el 40. Código fuente. void selectionSort(int numbers[], int array_size) { int i, j; int min, temp; for (i =
| Página siguiente |