tiempos de ejecucion

Universidad Católica del Maule
Facultad de Ciencia de Ingeniería
Ingeniería Civil Informática.

Algoritmos de
ordenamiento y
búsqueda

Alumno: Maydelin González Muñoz
Asignatura: Estructura de datos.
Profesor: Hugo Araya

Fecha de Entrega: 13/05/2013

Indice







Introducción………………………………………………….
Diseño de solución…………………………………………
Detalles deimplementación…………………………….
o Método burbuja…………………………………………………….
o Método Shell Sort…………………………………………………
o Método Quick Sort……………………………………………….
o Método de Búsqueda Binaria………………………………
o Método de Búsqueda Secuencial………………………….
Limitaciones……………………………………………………
Conclusiones…………………………………………………..

3
4
5
5
8
10
12
14
16
16

Introducción
Los algoritmos de ordenamiento nos permite, como su nombre lo dice,
ordenar. En estecaso, nos serviran para ordenar valores asignados
aleatoriamente, ordenados e inversos. Nos centraremos en los métodos
más populares (Burbuja, Shell sort, Quick sort) analizando la
cantidad de comparaciones que suceden y el tiempo que demora en los
distintos sistemas operativos (Windows, Linux).
Un algoritmo de búsqueda es aquel que está diseñado para localizar un
elemento con ciertaspropiedades dentro de un conjunto de datos por
ejemplo, ubicar un número determinado dentro de un conjunto de
200000 datos.
Este informe nos permitirá conocer más a fondo cada método distinto de
Ordenamiento y de búsqueda, desde uno simple hasta el más complejo.
Se realizaran comparaciones en tiempo de ejecución, pre-requisitos de
cada algoritmo, funcionalidad, alcance, etc.

Diseño de laSolución

Para solucionar el problema, este se dividió en varios sub problemas:


Primero comprender en forma clara lo que se pide.



Especificar de que manera vamos a ordenar los datos de los
métodos de ordenamiento utilizados (aleatorios, ordenados e
invertidos).



Medir los tiempos de ejecución de cada algoritmo de ordenamiento
en Windows y en Linux y compararlos entre cada uno deellos y
ver su eficiencia.



Graficar

los

tiempos

de

ejecución

de

los

algoritmos

de

ordenamiento para obtener una idea más clara de lo que se nos
está solicitando.


Medir los tiempos de ejecución de cada algoritmo de búsqueda en
Windows y en Linux y compararlos entre cada uno de ellos y ver
su eficiencia.



Graficar

los

tiempos

deejecución

de

los

algoritmos

de

ordenamiento para obtener una idea más clara de lo que se nos
está solicitando.

Detalles de la Implementación

Método burbuja: El método de la burbuja es uno de los más simples,
es tan fácil como comparar todos los elementos de una lista contra
todos, si se cumple que uno es mayor o menor a otro, entonces los
intercambia de posición.
Por ejemplo,imaginemos que tenemos los siguientes valores:
5

6

1

0

3

Lo que haría una burbuja simple, seria comenzar recorriendo los valores
de izquierda a derecha, comenzando por el 5. Lo compara con el 6, con
el 1, con el 0 y con el 3, si es mayor o menor (dependiendo si el orden
es ascendiente o descendente) se intercambian de posición. Luego
continua con el siguiente, con el 6, y locompara con todos los
elementos de la lista, esperando ver si se cumple o no la misma
condición que con el primer elemento. Así, sucesivamente, hasta el
último elemento de la lista.
Para nuestro caso utilizaremos distintos conjuntos de datos generados
aleatorio, ordenado o inverso y se mide el tiempo de ejecución de cada
uno del conjunto de datos realizados en distintos sistemas operativos.
Lainformación se visualiza en la siguiente tabla:

SO
Algoritmo
N
1000
10000
100000
200000
300000
400000
500000
600000
700000
800000
900000
1000000

Ordenado
0
0
18
53
147
215
351
-

Windows
Burbuja
Inverso
0
1
31
116
201
399
613
-

Aleatorio
0
2
35
141
297
518
805
-

Tiempo en segundos

Método burbuja en Windows
850
800...