Ingerniero En Informática

Integrantes:
Mauricio Venegas M.
Francisco Velásquez F.
Profesor:
Sr. Mauricio Álvarez G.
Fecha:
31 de Marzo de 2012
Integrantes:
Mauricio Venegas M.
Francisco Velásquez F.
Profesor:
Sr. Mauricio Álvarez G.
Fecha:
31 de Marzo de 2012
Algoritmos de ordenamiento

Introducción

En el presente informe, destacamos el uso de los Algoritmos de búsqueda, árbol AVL y Binary Search,analizando el peor, mejor y caso promedio en lo que respecta su funcionalidad, además de analizar cómo va realizando sus tareas específicas para lo que fueron destinadas.
En este caso, éstos algoritmos nos permiten realizar todo tipo de búsquedas ya sea en algún arreglo o alguna matriz, la idea de éste presente trabajo es entender éste proceso y ver cómo se lleva a cabo.
También se mostrará elseguimiento de dichos algoritmos mediante un pseudolenguaje, el cuál mostrará en forma simple el funcionamiento de éstos y se mostrará cómo va variando su funcionalidad de acuerdo a la cantidad de datos disponibles.

Binary Search
Antecedentes
Algoritmo del tipo “Divide y vencerás”, el cual consiste en tomar un problema original de forma ordenada y subdividirlos en otros problemas más simples demás o menos la mitad del tamaño, creado en 1946 por John Mauchly, éste algoritmo se dice que tiene sus orígenes de la antigua Babilonia en el año 200 A.C, en el cual planteaban una lista ordenada de números para facilitar la búsqueda de algún elemento dentro de esa lista.

Mejor, peor y caso promedio
Mejor caso
En el caso de Binary Search el mejor caso es cuando se realiza una sola comparación,es decir cuando el elemento buscado es el primer punto medio obtenido de la suma del índice inicial y el último.
Peor caso
El peor caso se da cuando requiere un tiempo de O(logN), es decir mientras más divisiones y comparaciones con el punto medio y además el elemento no es encontrado, sería el peor caso para éste algoritmo.
Caso promedio
En éste caso, se dice que el caso promedio es igual alpeor caso y que tiene una notación de O(logN), en el caso de que un elemento no sea encontrado.

Complejidad tiempo y espacio
A continuación se entregan resultados de pruebas hechas con el algoritmo de búsqueda Binaria en Arreglos con 50, 100, 500, 1000, 5000, 10000, 50000, 100000 y 500000

Datos ordenados
| Tiempo promedio | Cantidad Iteraciones |
Con 50 datos | 00:00:00.0000021 | 5 |Con 100 datos | 00:00:00.0000029 | 11 |
Con 500 datos | 00:00:00.0000051 | 17 |
Con 1000 datos | 00:00:00.0000055 | 19 |
Con 5000 datos | 00:00:00.0000068 | 23 |
Con 10000 datos | 00:00:00.0000108 | 25 |
Con 50000 datos | 00:00:00.0000145 | 29 |
Con 100000 datos | 00:00:00.0000102 | 33 |
Con 500000 datos | 00:00:00.0000153 | 37 |

Resultado experimental prototipo
Trazabilidad deejemplo
Supongamos el siguiente arreglo ordenado de 5 datos, con los índices “i” y “j”, nos ponemos en el caso de buscar el número 7.
5 | 7 | 15 | 21 | 30 |
j
j
i
i

21 | 30 |
15 |
Primero se saca el punto medio del arreglo sumando la posición inicial “i” (en este caso 0) con el índice “j”(4), luego se divide en 2 , dicho resultado será el punto medio (2) y se utilizara como primercomparativo.
5 | 7 |

i j
Luego se determina si el punto medio es igual al número buscado, de no ser así se ve si el punto medio es mayor o menor al elemento a buscar, en este caso, nuestro punto medio es mayor al elemento a buscar entonces se omite el resto del arreglo que es mayor al punto medio quedando como resultado lo siguiente
5 | 7 | 15 |

ij
7 |
Como se puede apreciar anteriormente, ahora el punto medio es el último elemento, es decir que ahora el índice “j” toma el índice del punto medio.
Posteriormente se vuelve a sumar el índice del primer elemento con el índice del último para obtener un nuevo punto medio.
4 |
12 |

i j
Al igual que antes se vuelve a comparar el punto medio con el...