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

Métodos de Ordenamiento y Búsqueda de Información

No description
by

Jared Solano Olivas

on 16 December 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Métodos de Ordenamiento y Búsqueda de Información

Métodos de Ordenamiento y Búsqueda de Información
Métodos de búsqueda.
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.

Los métodos de búsqueda se clasifican en:

Ordenación externa.
Son necesarios cuando los datos que se quiere ordenar no cabe en la memoria principal (RAM) de la computadora y por tal motivo se encuentran almacenados en un dispositivo secundario externo (el disco duro, cinta, memoria usb, etc.). La mayoría de estos algoritmos utilizan la técnica de divide y vencerás y la intercalación de archivos, para aplicar el ordenamiento.
Los algoritmos de ordenación externa más comunes son dos:

- Intercalación directa o mezcla directa y
- Mezcla natural o mezcla equilibrada.
Búsqueda interna.
Es aquella en la que todos los elementos de la estructura estática (arreglo) o dinámica (lista ligada o árbol) se encuentran almacenados en la memoria principal de la computadora.

Los métodos de búsqueda interna más importantes son:

Ordenación interna.
Sus implementaciones son muy variadas, de manera que la elección del algoritmo adecuado debe realizarse con criterios de eficiencia (tiempo y ejecución) y en función de la memoria disponible. Dividiremos los métodos en
dos grandes grupos:
- Directos
- Logarítmicos
Tipos de Ordenamiento
Son mecanismos que muestran múltiples soluciones para un mismo problema, y que cada solución algorítmica tiene sus propias ventajas y desventajas.
Los métodos de ordenamiento que trabajan con estructuras de datos residentes en memoria
principal se denominan Ordenamientos Internos, mientras que las implementaciones que utilizan
estructuras de datos residentes en archivos se conocen como Ordenamientos externos.

Los métodos directos, son los más simples y fáciles de entender, son eficientes cuando se trata de una cantidad de datos pequeña
Los métodos directos más conocidos son:

- Ordenación por intercambio.
- Ordenación por inserción.
- Ordenación por selección.
Los métodos logarítmicos, son más complejos, difíciles de entender y son eficientes en grandes cantidades de datos.
Los métodos directos más conocidos son:
-Shell sort
-Quick sort
-Radix
Consiste en comparar dos elementos del arreglo y determinar si existe un intercambio entre ellos
Cada elemento se compara con los elementos contiguos de su izquierda de uno por uno, para lograr su ordenamiento
Es encontrar el elemento más pequeño (grande), en orden ascendente de la lista, e intercambiarlo con el elemento que ocupa la primera posición en la lista, a continuación se busca el siguiente elemento más pequeño y se transfiere a la segunda posición. Se repite el proceso hasta
que el último elemento ha sido transferido a su posición correcta.

La idea centrar de este algoritmo consiste en realizar de forma sucesiva una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor. En la primera pasada la partición es de longitud 1 y la fusión produce secuencias ordenadas de longitud 2. En la segunda pasada la partición es de longitud 2 y la fusión produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la partición sea menor o igual al número de elementos del archivo original.
Mezcla natural.
Intercalación directa.
La idea central de este algoritmo consiste en realizar particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias ordenadas de tamaño fijo previamente determinadas, como la intercalación directa. Posteriormente se realiza la fusión de esas secuencias ordenadas, alternándolas entre los dos archivos auxiliares. Repitiendo este proceso, se logra que el archivo quede completamente ordenado.Para aplicar este algoritmo, se necesitarán cuatro archivos.
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.
Shell sort
Es una técnica basada en otra conocida con el nombre divide y vencerás, que permite ordenar una cantidad de elementos en un tiempo proporcional a n2 en el peor de los casos o a n log n en el mejor de los casos. El algoritmo original es recursivo, como la técnica en la que se basa.


Quick Sort
El método de ordenación radix es un algoritmo que ordena datos procesando sus elementos de forma individual, según la posición que ocupan dentro del dato. Los datos numéricos "los por dígitos" y "los datos alfabéticos por letras".
Radix
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.
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.
Ordenación por selección
Ordenación por inserción:
Ordenación por intercambio:
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.
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.

- Secuencial o lineal.

- Binaria.

- Hash (transformación de claves)

- Búsqueda interna.

- Búsqueda externa.
Búsqueda Externa
La búsqueda externa es aquella en la que todos los elementos se encuentran almacenados en un archivo, el cual se encuentra en un dispositivo de almacenamiento secundario como un disco duro, una cinta o una memoria usb.

Los métodos de búsqueda externa más importantes son:
- Secuencial.

- Binaria.

- Hash (transformación de claves)
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.
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.
Integrantes
Ponza Guadalupe Miguel
Solano Olivas Jared
Villegas Villanueva Jonathan Abraham
Bibliografías
-https://sites.google.com/site/estdatjiq/home/unidad-vi
-https://sites.google.com/site/estdatjiq/home/unidad-v
-http://www.paginasprodigy.com/edserna/cursos/estddatos/notas/Unidad3.Ordenamientos.pdf
http://delta.cs.cinvestav.mx/~adiaz/anadis/Sorting2.pdf
1.Generar un ciclo que inicie desde uno hasta el número de elementos del arreglo.
2.Generar un segundo ciclo dentro del anterior que inicie desde cero hasta el número de elementos del arreglo menos dos.
3.Dentro del segundo ciclo debe existir una comparación que determina el tipo de ordenamiento (ascendente o descendente) entre el primer elemento (posición generado por el segundo ciclo) y el segundo elemento (el que le sigue), si la respuesta a la condición es verdadera se realiza un intercambio entre los dos elementos.
4.Para realizar el intercambio se genera un almacenamiento temporal, el cual guarda el dato del primer elemento, el segundo elemento toma el lugar del primero y en el lugar del segundo se coloca lo que contiene el almacenamiento temporal.
-Generar un ciclo que se encargue de controlar el tamaño que deben tener los incrementos.
1. Este ciclo debe iniciar con la división del tamaño del arreglo entre dos.
2. Mientras que el incremento sea mayor a cero debe continuar.
3. Y el cambio de incremento se elige de entre dos opciones: un uno o la división del incremento anterior entre dos.

-Un segundo ciclo dentro del anterior, controla el número de comparaciones que se deben hacer según el tamaño del incremento.
1. El control de este ciclo debe iniciar con el incremento generado anteriormente.
2. Mientras el control del ciclo sea menor que el tamaño del arreglo.
3. El control debe cambiar de uno en uno.

-Un tercer ciclo dentro del segundo controla en que momento se detienen las comparaciones o se hacen los posibles intercambios entre los elementos.
1. El control de este ciclo debe iniciar con el valor del ciclo anterior.
2. Mientras que el control sea mayor o igual al incremento del primer ciclo y el elemento del arreglo de la posición del control de este ciclo menos el incremento, sea mayor que el elemento del arreglo de la posición control de este ciclo, realice los intercambios entre estas posiciones.
3. Y el control se decremente con el valor del incremento.

1.Buscar el mínimo elemento de la lista
2.Intercambiarlo con el primero
3.Buscar el siguiente mínimo en el resto de la lista
4.Intercambiarlo con el segund
-Generar un ciclo que se encargue de controlar el tamaño que deben tener los incrementos.
1. Este ciclo debe iniciar con la división del tamaño del arreglo entre dos.
2. Mientras que el incremento sea mayor a cero debe continuar.
3. Y el cambio de incremento se elige de entre dos opciones: un uno o la división del incremento anterior entre dos.

-Un segundo ciclo dentro del anterior, controla el número de comparaciones que se deben hacer según el tamaño del incremento.
1. El control de este ciclo debe iniciar con el incremento generado anteriormente.
2. Mientras el control del ciclo sea menor que el tamaño del arreglo.
3. El control debe cambiar de uno en uno.

-Un tercer ciclo dentro del segundo controla en que momento se detienen las comparaciones o se hacen los posibles intercambios entre los elementos.
1. El control de este ciclo debe iniciar con el valor del ciclo anterior.
2. Mientras que el control sea mayor o igual al incremento del primer ciclo y el elemento del arreglo de la posición del control de este ciclo menos el incremento, sea mayor que el elemento del arreglo de la posición control de este ciclo, realice los intercambios entre estas posiciones.
3. Y el control se decremente con el valor del incremento.


1: Debe elegir uno de los elementos del arreglo al que llamaremos pivote.
2: Debe acomodar los elementos del arreglo a cada lado del pivote, de manera que del lado izquierdo queden todos los menores al pivote y del lado derecho los mayores al pivote; considere que en este momento, el pivote ocupa exactamente el lugar que le corresponderá en el arreglo ordenado.
3: Colocado el pivote en su lugar, el arreglo queda separado en dos subarreglos, uno formado por los elementos del lado izquierdo del pivote, y otro por los elementos del lado derecho del pivote.
4: Repetir este proceso de forma recursiva para cada subarreglo mientras éstos contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
1. Determinar cuál es la mayor cantidad de dígitos del elemento mayor del arreglo.
2. Crear un arreglo de colas, que permita almacenar cana uno de los dígitos del 0 al 9.
3. Crear cada posición del arreglo como un objeto que permita almacenar los elementos en cada cola, según el índice que le corresponde.
-Generar un ciclo que determine el número de digito que se esta procesando y el factor que permite encontrar el digito.
1. Inicializar el número de digito y el factor en uno;
2. Mientras el digito sea menor o igual a la cantidad de dígitos encontrados en le paso uno.
3. El número de digito se debe incrementar de uno en uno.

-Crear un segundo ciclo que se encuentra dentro del anterior y que se encarga de recorrer todo el arreglo desde la posición inicial hasta la final del arreglo.
1. Iniciar el control del ciclo en cero.
2. Mientras el control sea menor al tamaño del arreglo, continuamos en el ciclo.
3. El control del ciclo se cambia de uno en uno.

-Generar un segundo ciclo que se encuentra dentro del primero, al igual que el anterior y este controla el paso de los elementos de las colas al arreglo nuevamente.
1. El control de este ciclo inicia desde la cola cero, al igual que el índice que controla el arreglo de los elementos.
2. Mientras el control sea menor a diez continua dentro del ciclo.
3. El control del ciclo se incrementa de uno en uno.


¿Qué método de Búsqueda es el más funcional y por qué?
El método mas funcional es el secuencial ya que es el mas fácil y consiste en revisar el archivo elemento por elemento hasta encontrar el dato que se esta buscando
¿Qué método de Ordenamiento es el más funcional y por qué?
El método de ordenamiento mas funcional es el shell short mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga pasos más grandes hacia la posición que debe ocupar
Full transcript