Algoritmo de búsqueda

Solo disponible en BuenasTareas
  • Páginas : 8 (1866 palabras )
  • Descarga(s) : 0
  • Publicado : 5 de diciembre de 2010
Leer documento completo
Vista previa del texto
Algoritmo de búsqueda
Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o la mejor movida en una partida de ajedrez.
La variante más simple del problema es la búsqueda de un número en un vector.

Búsqueda secuencial:Consiste en la revisión elemento por elemento del arreglo hasta encontrar el dato buscado, o hasta llegar al final del arreglo, sin haberlo encontrado. Se puede diferenciar entre buscar en un arreglo desordenado y buscar en un arreglo ordenado.
 
Búsqueda en arreglos desordenados
Algoritmo que busca secuencialmente el elemento X en el arreglo desordenado V, con N elementos.

Secuencialdesordenado(V, N, X)Inicio Declarar i:entero Declarar bandera: booleano  i 1 Bandera FALSO Mientras Que ((i<=N) y (Bandera=FALSO)) haga Si (V[i]=X) entonces Bandera VERDADERO Sino i i+1 Fin si Fin MQ Si (bandera=VERDADERO) entonces Imprimir(“El elemento está en la posición i”); Sino Imprimir(“El elemento no está en el arreglo”) Fin siFin |

Búsqueda dicotómica (binaria):

Labúsqueda binaria, sirve exclusivamente para arreglos ordenados, consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el central, , en caso de no ser iguales se redefinen los extremos del intervalo (según si el elemento central es mayor o menor que el buscado). El proceso termina cuando se encuentra el elemento o cuando se anula el intervalo de búsqueda.
Algoritmoque busca el elemento X mediante búsqueda binaria en el arreglo ordenado V con N elementos.

binaria(V, N, X)Inicio Declarar izq, cen, der: entero Declarar bandera: booleano  Izq 1 Der N Bandera FALSO Mientras Que ((izq<=der) y (Bandera=FALSO)) haga Cen parteentera((izq+der)/2) Si (X=V[cen]) entonces Bandera VERDADERO Sino Si (X>V[cen]) entonces izq cen+1 Sinoder cen-1 Fin si Fin si Fin MQ Si (bandera=VERDADERO) entonces Imprimir(“El elemento está en la posición cen”); Sino Imprimir(“El elemento no está en el arreglo”) Fin siFin  |

Algoritmos de Ordenamiento
Ordenamiento de burbuja:
El Ordenamiento de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenadacon 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 algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como elmétodo del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar
Ejemplo:.

MÉTODO BURBUJA.
El bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente manera: Se recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglotantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo de posición en posición hasta ponerlo en su lugar.

Pseudocódigo del método de la burbuja:
|

Ordenamiento por inserción

El ordenamientopor inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se...
tracking img