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  |