PDF de programación - TP 1: Algoritmos de ordenamiento - Estructura de datos III

Estructura de datos III



TP 1:

Algoritmos de ordenamiento



___________________________________________________________________
Estructura de datos III
Algoritmos
Página 1 de 33

de

ordenamiento_byPerses.doc





Autor:
[email protected]

Sede:
San Isidro

___________________________________________________________________
Estructura de datos III
Algoritmos
Página 2 de 33

de

ordenamiento_byPerses.doc

Algoritmos de ordenamiento



Resumen
El siguiente trabajo desarrolla el tema de la performance en distintos algoritmos de
ordenamiento y presenta una comparativa de cada uno de ellos, como también el
órden de complejidad de los mismos.
Los algoritmos analizados son:

• Bubble sort
• Selection sort
•
Insertion sort
• Shell sort
• Heap sort
• Merge sort
• Quick sort

Las implementaciones de los algoritmos han sido realizadas en c++.



___________________________________________________________________
Estructura de datos III
Algoritmos
Página 3 de 33

de

ordenamiento_byPerses.doc

Indice

Introducción.......................................................................................................................................... 4
Análisis de los algoritmos ................................................................................................................ 5
Bubble sort........................................................................................................................................ 5
Selection sort................................................................................................................................... 6
Insertion sort ................................................................................................................................... 7
Merge sort......................................................................................................................................... 9
Quick sort........................................................................................................................................ 14
Heap Sort ........................................................................................................................................ 16
Shell sort ......................................................................................................................................... 17
Conclusiones ....................................................................................................................................... 20
Apéndice............................................................................................................................................... 21
Apéndice 1 - Código fuente del Trabajo Práctico............................................................. 21
Apendice 2 - Análisis de Algoritmos...................................................................................... 30
Apendice 3 - Referencias........................................................................................................... 33



___________________________________________________________________
Estructura de datos III
Algoritmos
Página 4 de 33

de

ordenamiento_byPerses.doc



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.

___________________________________________________________________
Estructura de datos III
Algoritmos
Página 5 de 33

de

ordenamiento_byPerses.doc

Comparativa de algoritmos



o
p
m
e
i
T

400
350
300
250
200
150
100
50
0
-50

0

2000

4000
6000
Elementos

8000

10000

Poly. ( Bubble)
Poly. ( Insertion)
Poly. ( Selection)
Poly. ( Quick)
Poly. ( Shell)
Poly. ( Heap)
Poly. ( Merge)



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

o
p
m
e
i
T

400
350
300
250
200
150
100
50
0

0

2000

4000

6000

8000

10000

Elementos



___________________________________________________________________
Estructura de datos III
Algoritmos
Página 6 de 33

de

ordenamiento_byPerses.doc

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} <-- Se cambia el 21 por el 40.
{21,4,40,9,10,35} <-- Se cambia el 40 por el 4.
{21,4,9,40,10,35} <-- Se cambia el 9 por el 40.
{21,4,9,10,40,35} <-- Se cambia el 40 por el 10.
{21,4,9,10,35,40} <-- Se cambia el 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).

___________________________________________________________________
Estructura de datos III
Algoritmos
Página 7 de 33

de

ordenamiento_byPerses.doc

Selection sort

o
p
m
e
T

i

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 = 0; i < array_size-1; i++){
min = i;
for (j = i+1; j < array_size; j++){
if (numbers[j] < numbers[min])
min = j;

___________________________________________________________________
Estructura de datos III
Algoritmos
Página 8 de 33

de

ordenamiento_byPerses.doc

}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}

Insertion sort



El insertion sort trabaja insertando el item en su lugar correspondiente al final de la
lista. Como el bubble sort, éste algoritmo se comporta como O(n2), pero a pesar de
tener el misma complejidad, este algoritmo es casi el doble más eficiente que el
bubble sort.

Insertion sort

o
p
m
e
i
T

250

200

150

100

50

0

0

2000

40