sábado, 30 de mayo de 2009

Metodo De Busqueda

BÚSQUEDA. La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. A menudo un programador estará trabajando con grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si un arreglo contiene un valor que coincide con algún valor clave o buscado.Siendo el array de una dimensión o lista una estructura de acceso directo y a su vez de acceso secuencial, encontramos dos técnicas que utilizan estos dos métodos de acceso, para encontrar elementos dentro de un array: búsqueda lineal y búsqueda binaria.

Búsqueda Secuencial: La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda binaria, donde se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

Búsqueda Binaria. La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.

Metodos De Ordenamiento

¿Qué es ordenamiento?
Es la operación de arreglar los
registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.
El ordenamiento se efectúa con base en el
valor de algún campo en un registro.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.
Ej. de ordenamientos:
Dir. telefónico, tablas de contenido,
bibliotecas y diccionarios, etc.
El ordenar un
grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso alfanumérico, ascendente o descendente.
¿Cuándo conviene usar un
método de ordenamiento?
Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor
tiempo.
Tipos de ordenamientos:
Los 2 tipos de ordenamientos que se pueden realizar son: los internos y los externos.
Los internos:
Son aquellos en los que
los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc).
Los externos:
Son aquellos en los que
los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc).
Eficiencia en
tiempo de ejecución:
Una medida de
eficiencia es:
Contar el # de comparaciones (C)
Contar el # de movimientos de items (M)
Estos están en función de el #(n) de items a ser ordenados.
Un "buen
algoritmo" de ordenamiento requiere de un orden nlogn comparaciones.
La
eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo o vector a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2
Algoritmos de ordenamiento:
Internos:
Inserción directa.
Inserción directa.
Inserción binaria.
Selección directa.
Selección directa.
Intercambio directo.
Burbuja.
Shake.
Inserción disminución incremental.
Shell.
Ordenamiento de árbol.
Heap.
Tournament.
Sort particionado.
Quick sort.
Merge sort.
Radix sort.
Cálculo de
dirección.
Externos:
Straight merging.
Natural merging.
Balanced multiway merging.
Polyphase sort.
Distribution of initial runs.
Clasificación de los algoritmos de ordenamiento de información:
El hecho de que la
información está ordenada, nos sirve para poder encontrarla y accesarla de manera más eficiente ya que de lo contrario se tendría que hacer de manera secuencial.
A continuación se describirán 4
grupos de algoritmos para ordenar información:

Algoritmos de inserción:
En este tipo de
algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posición apropiada con respecto al resto de los elementos ya ordenados.
Entre estos
algoritmos se encuentran el de INSERCION DIRECTA, SHELL SORT, INSERCION BINARIA y HASHING.
Algoritmos de intercambio:
En este tipo de
algoritmos se toman los elementos de dos en dos, se comparan y se INTERCAMBIAN si no están en el orden adecuado. Este proceso se repite hasta que se ha analizado todo el conjunto de elementos y ya no hay intercambios.
Entre estos algoritmos se encuentran el BURBUJA y QUICK SORT.
Algoritmos de selección:
En este tipo de algoritmos se SELECCIONA o se busca el elemento más pequeño (o más grande) de todo el conjunto de elementos y se coloca en su posición adecuada. Este
proceso se repite para el resto de los elementos hasta que todos son analizados.Entre estos algoritmos se encuentra el de SELECCION DIRECTA.
Algoritmos de enumeración:
En este tipo de algoritmos cada elemento es comparado contra los demás. En la comparación se cuenta cuántos elementos son más pequeños que el elemento que se está analizando, generando así una ENUMERACION. El número generado para cada elemento indicará su posición.
Los
métodos simples son: Inserción (o por inserción directa), selección, burbuja y shell, en dónde el último es una extensión al método de inserción, siendo más rápido. Los métodos más complejos son el quick-sort (ordenación rápida) y el heap sort.
A continuación se mostrarán los
métodos de ordenamiento más simples.

METODO DE INSERCIÓN.
Este
método toma cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó).
Procedimiento Insertion Sort
Este
procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el número de elementos que contiene a[].
paso 1: [Para cada pos. del arreglo] For i <- 2 to N do
paso 2: [Inicializa v y j] v <- a[i]
j <- i.
paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do
paso 4: [Recorre los
datos mayores] Set a[j] <- a[j-1],
paso 5: [Decrementa j] set j <- j-1.
paso 5: [Inserta v en su posición] Set a[j] <- v.
paso 6: [Fin] End.

MÉTODO DE SELECCIÓN.
El
método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.
Procedimiento Selection Sort
paso 1: [Para cada pos. del arreglo] For i <- 1 to N do
paso 2: [Inicializa la pos. del menor] menor <- i
paso 3: [Recorre todo el arreglo] For j <- i+1 to N do
paso 4: [Si a[j] es menor] If a[j] < a[menor] then
paso 5: [Reasigna el apuntador al menor] min = j
paso 6: [Intercambia los
datos de la pos.
min y posición i] Swap(a, min, j).
paso 7: [Fin] End.

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 arreglo tantas 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.
Procedimiento Bubble Sort
paso 1: [Inicializa i al final de arreglo] For i <- N down to 1 do
paso 2: [Inicia desde la segunda pos.] For j <- 2 to i do
paso 4: [Si a[j-1] es mayor que el que le sigue] If a[j-1] < a[j] then
paso 5: [Los intercambia] Swap(a, j-1, j).
paso 7: [Fin] End.

MÉTODO DE SHELL.
Ordenamiento de disminución incremental.
Nombrado así debido a su inventor Donald Shell.
Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El
valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo
valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.
Al principio del
proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
"Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos."
Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
El
método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.
Procedimiento Shell Sort;
const
MAXINC = _____;
incrementos = array[1..MAXINC] of integer;
var
j,p,num,incre,k:integer;
begin
for incre := 1 to MAXINC do begin /* para cada uno de los incrementos */
k := inc[incre]; /* k recibe un tipo de incremento */
for p := k+1 to MAXREG do begin /* inserción directa para el
grupo que se encuentra cada K posiciones */
num := reg[p];
j := p-k;
while (j>0) AND (num < reg[j]) begin
reg[j+k] := reg[j];
j := j - k;
end;
reg[j+k] := num;
end
end
end;