Metodos de ordenamiento y busqueda

REPÚBLICA BOLIVARIANA DE VENEZUELA.

MINISTERIO DEL PODER POPULAR PARA LA DEFENSA.

UNIVERSIDAD NACIONAL EXPERIMENTAL DE LA FUERZA ARMADA.

UNEFA-LARA

LENGUAJE DE PROGRAMACION II

TRABAJO

METODOS DE ORDENAMIENTO Y BUSQUEDA

BARQUISIMETO, ABRIL DE 2013.

REPÚBLICA BOLIVARIANA DE VENEZUELA.

MINISTERIO DEL PODER POPULAR PARA LA DEFENSA.

UNIVERSIDAD NACIONAL EXPERIMENTAL DE LA FUERZA ARMADA.

UNEFA-LARA

LENGUAJE DE PROGRAMACION II

TRABAJO

METODOS DE ORDENAMIENTO Y BUSQUEDA

Sección: 5t1-Is

Área: Lenguaje de Programación.

Profesora: Marian

BARQUISIMETO, ABRIL DE 2013.

INDICE

Contenido pág.

Introducción______________________________________________________________4

Algoritmos De Ordenamiento________________________________________________5

Quicksort________________________________________________________________5

Descripción_____________________________________________________________6-7

Técnicas de reposicionamiento______________________________________________7-8

Transición a otro algoritmo__________________________________________________8

Ejemplo_______________________________________________________________9-10

Ordenamiento Por Mezcla__________________________________________________11

Descripción_____________________________________________________________11

Hashing________________________________________________________________12

Dirección ¬ H(clave)____________________________________________________12-13

Función Módulo (por división)______________________________________________13

Función Centro de Cuadrados______________________________________________13

Función Plegamiento______________________________________________________14

Función Truncamiento_____________________________________________________14

Tratamiento de colisiones__________________________________________________14

Prueba lineal__________________________________________________________14-15

Conclusión______________________________________________________________15

INTRODUCCION

Los algoritmos de ordenamiento son un conjunto de pasos o instrucciones que permiten ordenar de forma deseada una cadena de caracteres o una serie de números en un orden deseado. Los algoritmos de búsqueda son aquellos que están diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos, estos algoritmos pueden combinarse con algoritmos de encriptación como el hashing o hash que hacen que la búsqueda sea más precisa y segura.

Algunos algoritmos de ordenamiento conocidos son. Quick Sort, Merge Sort. Donde el primer algoritmo utiliza un pivote del cual a partir del cual comienza a colocar los números o letras por debajo del mismo y así sucesivamente ira seleccionando otro pivote hasta ordenar todo los datos. Mientras el segundo utiliza el método divide y vencerás, es decir, buscara ir dividiendo en cantidades iguales todos los datos introducidos y luego irlos comparado entre sí para obtener al final todos los datos ordenados de forma correcta.

ALGORITMOS DE ORDENAMIENTO

En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación o reordenamiento de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos.

Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort fue analizado desde 1956. Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventado hasta el día de hoy (por ejemplo, el ordenamiento de biblioteca se publicó por primera vez en el 2004). Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.

QUICKSORT

El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Descripción

El algoritmo trabaja de la siguiente forma:

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n).

En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

En el caso promedio, el orden es O(n•log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Técnicas de elección del pivote:

El algoritmo básico del método Quicksort consiste en tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la partición en que se elija, el algoritmo será más o menos eficiente.

Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista.

Otra opción puede ser recorrer la lista para saber de antemano qué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n•log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio.

La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote.

Técnicas de reposicionamiento

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la recursividad.

Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:

Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).

Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones.

Repetir esto hasta que se crucen los índices.

El punto en que se cruzan los índices es la posición adecuada para colocar

...