Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

METODOS DE BUSQUEDA Y ORDENAMIENTO

No description

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of METODOS DE BUSQUEDA Y ORDENAMIENTO

METODOS DE BUSQUEDA
BUSQUEDA INTERNA
BUSQUEDA EXTERNA
METODO DE ORDENAMIENTO EXTERNO
METODO DE ORDENAMIENTO INTERNO
METODOS DE ORDENAMIENTO
ORDENAMIENTO INTERNO
METODOS DE BUSQUEDA Y ORDENAMIENTO
Busqueda Interna
LOS METODOS DE BUSQUEDA SE CLASIFICAN EN:

La búsqueda es la operación más importante en el procesamiento de información, ya que permite recuperar datos previamente almacenados. El resultado de una búsqueda puede ser un éxito, si se encuentra la información o un fracaso, si no la encuentra.
La búsqueda se puede aplicar sobre elementos previamente ordenados o sobre elementos desordenados, en el primer caso la búsqueda es más fácil, en cambio en el segundo se dificulta un poco más el proceso, sobre todo cuando de se trata de encontrar una cantidad de elementos similares.

Busqueda Externa
{
Secuencial
Binaria
Hash
{
Secuencial
Binaria
BUSQUEDA SECUENCIAL
El método de búsqueda secuencial externa consiste en revisar el archivo elemento por elemento hasta encontrar el dato que se esta buscando, o hasta llegar al final del archivo. Este método de búsqueda se puede aplicar a archivos ordenadas o desordenadas.
Si la búsqueda se aplica a un archivo desordenado y el elemento que se está buscando existe más de una vez, el proceso de búsqueda debe continuar hasta que se llegue al fin del archivo.

BUSQUEDA BINARIA
El método de búsqueda binaria externa utiliza el mismo principio que la búsqueda binaria interna. Divide el total de elementos del archivo en dos, comparando el elemento buscado con el central, en caso de no ser iguales se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible.
El archivo debe estar ordenado y se debe conocer el número de elementos del mismo para aplicar este método.

BUSQUEDA SECUENCIAL
El método de búsqueda secuencial consiste en revisar la estructura de datos elemento por elemento hasta encontrar el dato que estamos buscando, o hasta llegar al final de la estructura de datos.
Normalmente cuando una función de búsqueda concluye con éxito, lo que interesa es conocer en qué posición fue encontrado el elemento buscado.
La búsqueda secuencial se puede aplicar a estructuras de datos ordenadas o desordenadas.
Si se aplica a una estructura desordenada y el elemento que se está buscando existe más de una vez en la estructura, el proceso de búsqueda debe continuar hasta que se llegue al fin de la estructura.

BUSQUEDA BINARIA
El método de búsqueda binaria divide el total de los elementos en dos, comparando el elemento buscado con el central, en caso de no ser iguales, se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible.
Debemos destacar que este método de búsqueda solo funciona con estructuras de datos previamente ordenadas, dividiendo cada vez a la mitad el proceso de búsqueda, lo que hace que el método sea más eficiente.

BUSQUEDA DE HASH
El método de búsqueda hash o por transformación de clave aumenta la velocidad de búsqueda sin necesidad de que los elementos estén previamente ordenados, comparándolo con los métodos anteriores. Además tiene la ventaja de que el tiempo de búsqueda es independiente del número de elementos de la estructura que los almacena.
Este método permite que el acceso a los datos sea por una llave que indica directamente la posición donde están guardados los datos que se buscan. Prácticamente trabaja con una función que transforma la llave o dato clave en una dirección (índice) dentro de la estructura y que en ocasiones puede generar una colisión, que se define como una misma dirección para dos o más claves distintas.

Funciones de Hash
{
Funcion Modulo (por division)
Funcion Cuadrada
Funcion Plegamiento
Funcion Truncamiento
ORDENAMIENTO EXTERNO
Burbuja
Quick Sort
-------------------------------
-------------------------------
|
|
|
|
|
|
----------------
Intercalacion
Mezcla Directa
Mezcla Natural
{
Ordenación por intercambio (burbuja)
Debido a que las estructuras de datos son utilizadas para almacenar información, para poder recuperar esa información de manera eficiente es deseable que aquella esté ordenada. Existen varios métodos para ordenar las diferentes estructuras de datos básicas.
Metodo de QuickSort
Metodo de Shell Sort
Metodo de Radix
Metodo de Intrcalacion
Mezcla directa
Mezcla neutral
El método d la burbuja es uno de los métodos relativamente más sencillo e intuitivo, pero también resulta ser muy
ineficiente.
Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada.
Este método recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
La idea central de este algoritmo consiste en los siguiente:
1. Elegir un elemento de la lista de elementos a ordenar (pivote).

2. 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.

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

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

Shell Sort
Shell sort lleva este nombre en honor a su inventor, Donald Shell, que lo publicó en 1959. La idea
básica de este método es distribuir el arreglo de manera que se genere una matriz de valores
donde cada elemento es comparado de manera adyacente empleando un mecanismo de inserción
directa simple, dicho rango que genera grupos de manera matricial que es reducido gradualmente
hasta estabilizarse en un valor uniforme de 1.
Radix
Es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.
Existen dos clasificados del método de Radix:

LSD ---->>>dígito menos significativo
MSD --->>>dígito más significativo
Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo.

Radix sort MSD trabaja en sentido contrario.
Full transcript