"MÈTODOS 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 valorde 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 datossignifica 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 valoresa 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 binaria.
Inserción directa.
Selección directa.
Selección directa.
Burbuja.
Shake.
Intercambio directo.
Shell.
Inserción disminución incremental.
Heap.
Tournament.
Ordenamiento de árbol.
Quick sort.
Sort particionado.
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étodossimples 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.
"FUNDAMENTO DE LOS ALGORITMOS DE ORDENAMIENTO".
"EJEMPLOS DE ALGORITMOS DE ORDENAMIENTO"
"POR 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étodossimples 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.
"POR INSERCCIÒ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ó).
"POR 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
"POR 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.
"POR COMBINACIÒN"
La idea central de este algoritmo consiste en la realización sucesiva de una partición y una funció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 o mezcla produce secuencias ordenadas de longitud 2. En la segunda pasada la partición es de longitud 2 y la fusión o mezcla produce secuencias ordenadas de longitud 4. Este proceso se repite hasta que la longitud de la secuencia para la partición sea mayor o igual que el número de elementos del archivo original.
Ejemplo
Si el archivo original es: [25] [57] [48] [37] [12] [92] [86] [33]
en la primera pasada se produce: [25 57] [37 48] [12 92] [33 86]
Segunda pasada: [25 37 48 57] [12 35 86 92]
Tercera Pasada: [12 25 33 37 48 57 86 92]
"MÈTODOS DE BUSQUEDA"
METODOS DE BUSQUEDA
Búsqueda interna.
Este tipo de búsqueda trabaja con elementos residentes en memoria principal.
Estos pueden estar almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas encadenadas y árboles).
Los métodos de búsqueda interna más importantes son:
METODO SECUENCIAL
Búsqueda Secuencial
La búsqueda secuencial en arreglos desordenados consiste básicamente en recorrer el arreglo de izq. A der. Hasta que se encuentre elemento buscado o se termine el arreglo, lo que ocurra primero.
Normalmente cuando una función de búsqueda concluye con éxito interesa conocer en que posición fue hallado el elemento buscado. Esta idea puede generalice para todos los métodos de búsqueda. El algoritmo de búsqueda secuencial en arreglos desordenados es el que se explica a continuación.
Secuencial Desordenado (V, N ,X)
{Este algoritmo busca secuencialmente el elemento x en el arreglo desordenado V, de N elementos. { I es una variable de tipo entero, BANDERA es una variable de tipo Booleano}
1. Hacer I <-1 y BANDERA <-Falso
2. Repetir mientras (I<=N) y (BANDERA=FALSO)
2.1 Si V[I] = x entonces
Hacer BANDERA <-VERDADERO
si no Hacer I <-I + 1
2.2 {Fin del condicional del paso 2.1}
3. {Fin del ciclo des paso 2}
4. Si BANDERA = VERDADERO entonces
Escribir "El elemento esta en la posición I"
si no Escribir "El elemento no esta en el arreglo"
5. {Fin del condicional del paso 4}
Secuencial desordenado2(V, N, X)
{ x es un elemento a buscar en el vector V de N elementos} { I es una variable de tipo entero, BANDERA es una variable de tipo booleano}
1. Hacer I<-1, BANDERA<- FALSO, j=1
2. Repetir mientras (I<=N)
2.1 Si V[I] = x
entonces A[J] = I, I=I+1, J=J+1
BANDERA <-VERDADERO
2.2 {Fin del 2.1}
3. {Fin del 2}
4. Si BANDERA = VERDADERO
Entonces
4.1 Repetir con J desde 1 hasta N
4.1.1 Escribir "El elemento esta en la posición A[J]"
4.2 {Fin del 4.1}
Si no escribir "No existe" 5.
{Fin del 4}
Secuencial Ordenado ( V, N, X)
{Este algoritmo busca secuencialmente el elemento x en el arreglo V, de N componentes. V esta ordenado crecientemente: V(1) <= v(2) <=.... <= V(N)} { I es una variable de tipo entero. BAND es una variable de tipo booleano}
1. Hacer I<-1 y BAND<- FALSO
2. Repetir mientras (I<=N) y (BAND = FALSO)
2.1 Si X=V(I) entonces Hacer BAND <-Verdadero
si no Hacer I<-I+1
2.2 {Fin del 2.1}
3. {Fin del 2}
4. Si BAND = VERDADERO
Entonces Escribir "El elemento esta en la posición I",I
Si no Escribir "El elemento no esta en el arreglo"
5. {Fin del 4}
LISTAS
Una lista es una colección de elementos llamados generalmente nodos. El orden entre los nodos se establecen por medio de apuntadores, es decir direcciones, o referencias a otros nodos la siguiente figura presenta la estructura de un nodo.
En general, un nodo consta de 2 partes:
En campo información que se da del tipo de datos que se quiere almacenar en la lista.
Un campo liga, de tipo apuntador, que se utiliza para establecer la liga o el enlace con otro nodo de la lista. Si el nodo fuera el último de la lista, este campo tendrá como valor: NIL (vacío). Al emplearse el campo liga para relacionar 2 nodos, no será necesario almacenar físicamente a los nodos en los espacios contiguos.
OPERACIONES CON LIGAS.
Las operaciones que pueden llevarse a cabo con listas son:
· Recorrido de lista
· Inserción de un elemento
· Borrado de un elemento
· Búsqueda de un elemento
Algoritmo que crea una lista
Crea Inicio ( P)
{ El algoritmo crea una lista, agregando cada nuevo nodo al inicio de la misma }. { P y Q son variables de tipo apuntador P apuntará al inicio de la lista}.
1. CREA ( P ) {Crea el primer nodo de la lista }
2. Leer P^. Información
3. Hacer P^. Liga
4. Repetir CREA ( Q)
Leer Q^. Información
Hacer Q ^. Liga<-P
Hacer P <-Q
5. Hasta que ya no haya más Información.
Crea Final ( P )
{ Este algoritmo crea una lista agregando cada nuevo nodo al final de la misma } { P y Q son variables apuntador. P apuntará al inicio de la lista }
1. Crea ( P ) { Crea el primer nodo de la lista }
2. Leer P ^. Información
3. Hacer P^. Liga NIL ,T <-P
4. Repetir
Crea ( Q )
Leer Q ^. Liga <-NIL
T ^ .Liga <-Q T <-Q
5. Hasta que no haya información.
Recorreiterativo ( P)
{ Este algoritmo recorre una lista cuyo primer nodo esta apuntado por P } { Q es una variable de tipo apuntador }
1. Hacer Q <-P
2. Repetir mientras Q <-NIL
Escribir Q ^. Información
Hacer Q<- Q ^.Liga { Apunta al siguiente nodo }
3. { Fin del ciclo del paso 2 }
Recorrecursivo ( P )
{ Esta algoritmo recorre una lista recursivamente P es el apuntador al nodo a visitar }
1. Si P != NIL
Entonces P ^. Información
Llamar a RECURSIVO con P^. Liga
2. { Fin del condicional del paso 1 }
Inserta Inicio(P, DATO)
{ Este algoritmo inserta un nodo al inicio de la lista. P es el apuntador al primer nodo de la lista, y DATO es la información que se almacenará en el nuevo nodo} { Q es una variable de tipo apuntador }
1. Crea ( Q )
2. Hacer Q ^. Información <-DATO
Q ^ . Liga <-P
P <-Q
Inserta Final( P, DATO)
{ Inserta un nodo al final de la lista }
1. Hacer T<- P
2. Repetir mientras T ^. Liga !=NIL
Hacer T<- T^. Liga
3. { Fin del paso 2 }
4. Crea Q
5. Hacer Q ^. Información <-DATO
Q ^. Liga <-NIL
T ^.Liga <-Q
INSERCION DE UN NODO ANTES / DESPUES DE OTRO
Insertantes( P, DATO , REF )
{ El algoritmo inserta un nodo antes de un nodo dado como referencia, REF. P es el apuntador al primer nodo de la lista , y dato es la información que se almacenará en el nuevo nodo }
1. Hacer Q <-P y BAND <-VERDADERO
2. Repetir mientras (Q ^. Información !=REF ) Y (BAND = VERDADERO )
2.1 Si Q Liga !=NIL
Entonces Hacer T<-Q y Q <-Q ^. Liga
Si no Hacer BAND <-FALSO
2.2 { Fin del condicional 2.1 }
3. { Fin del paso 2 }
4. Si BAND = VERDADERO
Entonces Crea ( X )
Hacer X ^.Información <-DATO
4.1. Si P = Q { Es el primer nodo }
Entonces Hacer X ^. Liga <-P
P <-X
Si no Hacer T ^. Liga <-X
X ^. Liga <-Q
4.2. { Fin del condicional del paso 4.1 }
5. { Fin del condicional del paso 4 }
ELIMINACION DE NODOS
Elimina Primero( P )
{ Este algoritmo borra el primer nodo de una lista P es el apuntado al primer nodo de la lista }
1. Hacer Q <-P
2. Si Q ^. Liga !=NIL { Verifica si la lista tiene un solo nodo }
Entonces Hacer P <-Q^. Liga
Si no Hacer P <-NIL
3. { Fin del condicional del paso 2 }
4. Quita ( Q )
ELIMINA NODO CON INFORMACION X
Elimina( P,X )
{ El algoritmo elimina un nodo con información X de la lista. P es el apuntador al primer nodo de la lista }
1. Hacer Q <-P , BAND <-VERDADERO
2. Repetir mientras ( Q ^. Información !=X ) y ( BAND =VERDADERO )
2.1. Si Q^. Liga !=NIL
Entonces Hacer T <-Q , Q <-Q ^.Liga
Si no Hacer BAND <-FALSO
2.2 { Fin del condicional del paso 2.1 }
3. { Fin del ciclo del paso 2 }
4. Si BAND = FALSO
Entonces Escribir " El elemento no fue encontrado "
Si no
4.1 Si P = Q
Entonces P <-Q^. Liga
Si no T ^. Liga <-Q ^. Liga
4.2 { Fin del paso 4.1 }
Quita ( Q )
5. { Fin del condicional 4 }
Inseta despues( P, DATO, REF )
1. Hacer Q <-P y BAND <-VERDADERO
2. Repetir mientras ( Q^. Información !=REF ) y ( BAND =VERDADERO)
2.1 Si Q^. Liga !=NIL
Entonces Hacer Q <-Q^. Liga
Si no Hacer BAND <-FALSO
2.2 { Fin del condicional del paso 2.1 }
3. { Fin del condicional del paso 2 }
4. Si BAND = VERDADERO
Entonces Crea ( X )
Hacer X ^. Información <-DATO
X ^. Liga <-Q^. Liga y Q^. Liga <-X
5. { Fin del paso 4 }
Elimina Ultimo (P)
1. Si P^.liga=NIL
Entonces Quita(P)
Hacer P<- NIL
Si no hacer Q <-P
1.1 Repetir mientras (Q^.liga !=NIL)
Hacer T <-Q y Q <-Q^Liga
1.2 {Fin de 1.1}
Hacer T^.liga <-NIL
Quita (Q)
2.{Fin del condicional 1}
Eliminar el nodo anterior (o posterior) al nodo con información X.
Eliminantes X ( P,X )
{Este algoritmo elimina el nodo anterior al nodo que contiene a X. P es el apuntador al primer nodo de la lista}
1. Si P ^.Información = X
Entonces Escribir "No hay nodo que proceda a X"
Si no Q <-P
T <-P
BAND <-FALSO
2.1 Repetir mientras (Q^. Información !=X) y (BAND = FALSO)
1..1 Si Q^. liga !=NIL
entonces Hacer Q<- P, T <-Q, Q <-Q^.liga
Si no Hacer BAND <-VERDADERO
1..2 { Fin del condicional 1.1.1}
2.1 {Fin del paso 1.1}
2.1 Si BAND = VERDADERO
entonces Escribir "el elemento no fue encontrado"
Si no
1..1 Si P^ .liga =Q{Elemento a eliminar es el primero}
Entonces Quita(P) P<- Q
Si no R^ .liga <-Q
Quita (T)
1..2 {Fin de 1.3.1}
2.1 {Fin de 1.3}
2. {Fin de 1}
BUSQUEDA DE UN ELEMENTO
Busca desordenada(P,X)
{Este algoritmo busca un elemento con información X, en una lista desordenada P es el primer apuntador al primer nodo de la lista}
1. Q <-P, BAND <-VERDADERO
2. Repetir mientras (Q^. Información !=X) y (BAND =VERDADERO)
2.1 Si Q^. liga !=NIL
Entonces Q <-Q^. liga
Si no BAND <-FALSO
2.1 {Fin del 2.11}
3. {Fin de 2}
4. Si BAND = FALSO
Entonces Escribir "El elemento no fue encontrado"
Si no Escribir "El elemento esta en la lista"
5. {Fin del condicional del paso 4}
Busca Ordenada (P,X)
{Este algoritmo busca al elemento con información X en una lista ordenada ascendentemente. P es el apuntador al primer nodo de la lista}
1. Q <-P, BAND <-VERDADERO
2. Repetir mientras (Q^ .información < X) y (BAND = VERDADERO)
2.1 Si Q^. liga !=NIL
Entonces Hacer Q <-Q^.liga
Si no BAND <-FALSO
2.2 {Fin de 2.1}
3. {Fin de 2.1}
4. Si Q^. Información =X
Entonces Escribir "El elemento esta en la lista".
Si no Escribir "El elemento no fue encontrado"
5. {Fin del condicional del paso 4}
Busca Recursivo (P,X)
{Este algoritmo busca recursivamente al elemento con informacion X en una lista. P es el apuntador al nodo a visitar}
1. Si P^ .Información =X.
entonces Escribir "El elemento esta en la lista"
Si no
1.1 Si P^. liga !=NIL
Entonces Llamar a Busca Recursiva (P^. liga, X)
Si no Escribir "El elemento no fue encontrado"
1.2 {Fin del condicional del Paso 1.1}
2. {Fin del condicional del paso 1}
Listas Circulares
Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero.
En el caso de la operación de recorrido de listas circulares, es necesario aclarar que se debe considerar algún criterio para detectar cuando se han visitado todos los nodos para evitar caer en ciclos infinitos. Una posible solución consiste en usar un nodo extra, llamado nodo de cabecera, para indicar el inicio de la lista. Este nodo contendrá información especial, de tal manera que se distinga de los demás y así podrá ser referencia al principio de la lista.
En los algoritmos presentados para operar con listas puede apreciarse claramente que solo se tiene acceso a un nodo y al sucesor de este. Si es necesitara su predecesor, por ejemplo, se tendrían que usar variables auxiliares. Una manera de evitar esto, que además tener acceso a los nodos en cualquier orden, pudiendo recorrer la lista del inicio y al fin o viceversa es definir listas doblemente encadenadas.
Lista Doblemente Encadenadas
Una lista doblemente encadenada es una colección de nodos, en la cual cada nodo tiene 2 apuntadores, uno de ellos apuntando a su predecesor (liga izquierda) y otro a su sucesor (liga derecha). Por medio de estos apuntadores se podrá avanzar o retroceder a través de la lista según se tomen las direcciones de uno u otro apuntador.
Escribir el procedimiento que elimine el nodo P de una lista doblemente encadenada no circular.
1. Hacer Q<-P
2. Si Q^. ligader !=NIL
Hacer R<-Q^. liga der.
N<-Q^. liga izq.
N^. liga der.<-R
R^. liga izq. <-N
Quita(Q).
3. (Fin de 2)
Si no
Si Q^. liga der. = NILL y Q. liga izq. = NILL
Hacer Quita(Q)
4. Si no Si Q^. liga der !=NIL
Hacer R <-Q^. liga der.
R^. liga izq. <-NIL
Quita(Q)
5. Fin de 4
Si no
6. Si Q^. liga izq !=NIL
Hacer R <-Q^. liga izq.
R^. liga der. <-NIL
Quita(Q)
7. Fin de 6.
Escribir un procedimiento para insertar un nodo en una lista doblemente encadenada no circular:
a) a la izquierda de P.
b) a la derecha de P.
Nota: En todos los ejercicios P es cualquier nodo.
a) Inserta derecha
1. Crear (R).
2. Hacer Q <-P^. liga der.
R^. liga der. <-Q.
R^. liga izq. <-P.
P^. liga der. <-R.
2.1 Si (Q !=NIL)
entonces Q^. liga izq. <-R
3. {Fin del paso 2.1.}
b) Inserta derecha.
1. Crear (R).
2. Hacer Q^. liga izq.
R^. liga der. <-P.
R^. liga izq. <-Q.
2.1 Si (Q !=NIL)
entonces Q^. liga der. <-R
3. {Fin del paso 2.1.}
Secuencial con listas
{El algoritmo busca secuencialmente al elemento x en la lista cuyo nodo inicial esta apuntado por P} {a es una variabl de tipo apuntador, BAND es una variable de tipo booleano}
1. Hacer 0<-P y BAND <-FALSO
2. Repetir mientras (Q==NULL<-FALSO)
a. Si Q.INFO=x
Entonces Hacer BAND <-Verdadero
Si no Hacer Q<-Q.liga
b. {Fin del condicional del paso 2.1}
3. {Fin del ciclo del paso 2}
4. Si BAND = VERDADERO
Entonces Escribir "El elemento esta en la lista"
Si no Escribir "El elemento no esta en la lista"
5. {Fin del condicional del paso 4}
Secuencial con lista encadenada
{El algoritmo busca secuencialmente al elemento x en una lista encadenada cuyo nodo inicial esta apuntado por P}
1. Hacer Q<-P y BAND<-FALSO
2. Repetir hasta que (Q.ligader=P) o (BAND=FALSO)
a. Si Q.info=x
Entonces Hacer BAND<-VERDADERO
Si no Hacer Q<-Q.ligader
b. {Fin del condicional del paso 2.1}
3. {Fin del paso}
4. Si(BAND=VERDADERO) o (Q.info=x)
Entonces escribir "El elemento esta en la lista"
Si no escribir "El elemento esta en la lista"
5. {Fin del condicional del paso 4}
Secuencial con lista doblemente encadenada (P,F,X)
{Este algoritmo busca secuencialmente al elemento x en la lista cuyo nodo inicial esta apuntando por P y cuyo nodo final esta apuntado por F} {Q es una variable de tipo apuntador, bandera es una variable de tipo booleano}
1. Hacer Q<-P
2. Repetir
2.1 Si Q.info=X
Entonces Hacer bandera<-verdadero
Si no Hacer Q<-Q.siguiente
Hacer sig<-Q.siguiente
2.2 {Fin del condicional del 2.1}
3. Hasta que (siguiente=P) o (BANDERA=VERDADERO)
Si Q.info=x
Entonces BANDERA=VERDADERO
Si no BANDERA=FALSO
4. Si BANDERA=VERDADERO
Entonces Escribir "El elemento esta en la lista"
Si no Escribir "El elemento no esta en la lista"
5. {Fin del condicional del paso 4}
BÚSQUEDA BINARIA
La búsqueda binaria 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 redefine los extremos del intervalo (Según el elemento central sea mayor o menor que el buscado) disminuyendo el espacio de búsqueda. El proceso concluye cuando el elemento es encontrado, o bien cuando el intervalo de búsqueda se anulo. Este método funciona únicamente para arreglos ordenados con cada iteración del método el espacio de búsqueda se reduce a la mitad, por lo tanto el numero de comparaciones a realizar se disminuye notablemente. Esta disminución resulta significativa cuanto más grande sea el tamaño del arreglo.
Binaria (V, N, X)
{ Este algoritmo busca el elemento x en el arreglo ordenado V de N componentes} {IZQ, CEN, DER son variables de tipo entero, BAND es una variable de tipo booleano}
1. Hacer IZQ<-1, Der<-N, BAND<- FALSO
2. Repetir mientras (IZQ<=DER) y (BAND=FALSO)
Hacer CEN<-(IZQ+DER)/w
a. SI X=V[CEN]
Entonces hacer BAND<-VERDADERO
Si no
2.1.1 Si X>V[CEN]
Entonces HACER IZQ<-CEN+1
Si no Hacer DER<-CEN-1
2.1.2{Fin del condicional del 2.1.1}
b. {Fin del condicional del 2.1}
3. {Fin del ciclo del paso 2} 4. Si BAND=VERDADERO
Entonces escribir "El elemento esta en la posición CEN"
Si no Escribir "El elemento no esta en el arreglo"
5. {Fin del condicional del 4}
BÚSQUEDA POR TRANSFORMACIÓN DE LLAVES (HASHING)
Supongase que tiene una colección de datos cada uno de ellos identificado por una clave. Es claro que resulta atractivo poder tener acceso a ellos de manera directa.
El método por transformación de llaves permite esto. Trabaja basándose en una función de transformación o función Hash (H) que convierte una clave dada en una dirección (indice) dentro del arreglo.
Dirección<-H(clave)
Tipos de funciones Función modulo(residuo)
H(k)=Kmod N +1
La función Hash aplicada a la clave da un indice del arreglo, lo que permite acceder directamente sus elementos.
Para trabajar con el método de búsqueda debe elegirse previamente:
1. Una función Hash que sea fácil de calcular y que distribuya uniformemente las claves.
2. Un metodo para resolver colisiones. Si estas se presentan se debe contar con algún metodo que genere posiciones alternas.
FUNCIÓN CUADRADO
Consiste en elevar al cuadrado la clave y tomar los digitos centrales como dirección. El número de digitos a tomar queda determinado por el rango del indice.
Sea K la clave del dato a buscar.
H(k)=digitos_centrales(k^2)+1
La suma de una unidad a los digitos centrales es para obtener un valor entre 1 y N.
Ejemplo: Sea N=100 el tamaño del arreglo y sus direcciones entre 1 y 100
Sea K1= 7259 Dos claves a los que deben asignarse posiciones en el arreglo.
Sea K2=9359
K1 al cuadrado = 52693081
K2 al cuadrado= 87590881
Por lo tanto: H(K1)=digitos_centrales (52 693 081) +1= 94
H(K2)=digitos_centrales ( 87 590 881) +1= 91
EN CASO DE COLISIONES
Prueba lineal
Consiste en que una vez detectada la colisión se debe recorre el vector secuencialmente a partir del punto de detección hasta el elemento.
El proceso de búsqueda concluye cuando el elemento es hallado o cuando se encuentra una posición vacia. Se trata al arreglo como una estructura circular. El siguiente elemento después del ultimo es el primero.
Prueba_Lineal (V, N, K) {El algoritmo busca el dato con clave K en el arreglo V de N elementos, resuelve el problema de colisiones por medio de l prueba lineal} {D, DX son variables de tipo entero}
1. Hacer D<--H(k) {Genera Dirección}
2. 2. Si V(D).Clave=k
Entonces: Escribir "El elemento esta en la posición D"
Si no: Hacer DX<--D+1
2.1 Hacer Mientras (V[DX].clave=k) y (V[DX]=vacio) y (DX=D)
Hacer DX<--DX+1
2.1.1 Si DX=N+1 entonces:
Hacer DX<--1
2.1.2 {Fin del condicional del paso 2.1.1}
2.2 {Fin del ciclo del paso 2.1}
2.3 Si V[DX].clave=k
Entonces: Escribir: "El elemento esta en la posición DX"
Si no: Escribir ""El elemento no esta en el arreglo"
2.4 {Fin del condicional del paso 2.3}
3. {Fin del condicional del paso 2}
ENCADENAMIENTO
Consiste en que cada elemento del arreglo tenga un apuntador a una lista ligada, la cual se irá generando e ira almacenando los valores colisionados am edida que se requiera. Es el método más eficiente debido al dinamismo propio de las listas.
Encadenamiento (V, N, K) {Este algoritmo busca el dato con clave V de N elementos. Resuelve el problema de las colisiones por medio de encadenamiento} {D es una variable de tipo entero Q es una variable de tipo apuntador}
1. Hacer D<--H(k)
2. Si V[D].clave=k
Entonces: Escribir "El elemento esta en la posición D"
Si no: Hacer Q<--V[D].sig
a. Hacer mientras (Q=vacio) y (Q.clave=k)
Hacer Q<--Q.liga
b. {Fin del ciclo del paso 2.1}
c. Si Q=vacio
i. Entonces: Escribir "El elemento no esta en la lista"
ii. Si no: Escribir "El elemento si esta en la lista"
d. {Fin del condicional del paso 2.3}
3. {Fin del condicional del paso 2}
"FUNDAMENTO DE LOS ALGORITMOS DE BUSQUEDA"
La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivos externos). Todos los algoritmos de búsqueda tienen dos finalidades: - Determinar si el elemento buscado se encuentra en el conjunto en el que se busca. - Si elelemento está en el conjunto, hallar la posición en la que se encuentra. En este apartado nos centramos en la búsqueda interna. Como principales algoritmos de búsqueda en arrays tenemos la búsqueda secuencial, la binaria y la búsqueda utilizando tablas de hash.
"SECUENCIAL"
Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del array hasta que éste se encuentre, o hasta que se llegue al final del array. La existencia se puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del array. A continuación se muestra el pseudocódigo del algoritmo:
Datos de Entrada:
vec: vector en el que se desea buscar el elemento
tam: tamaño del vector
dato: elemento que se quiere buscar.
Variables
pos: posición actual en el array
pos = 0
Mientras pos < tam:
Si vec[pos]== dato devolver verdadero y/o pos, de lo contrario:
pos = pos + 1
Fin (Mientras)
Devolver falso
"BINARIA"
Se utiliza cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones.
Este algoritmo esta altamente recomendado para buscar en arrays enormes: En uno de 50.000.000 elementos, tarda 26 iteraciones en ejecutarse, suponiendo que la búsqueda falla, sino, siempre tarda menos en buscarlo.
Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central), si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el arreglo.
A continuación se presenta el pseudocódigo del algoritmo, tomando como elemento inicial el elemento central del array.
Datos de Entrada:
vec: vector en el que se desea buscar el elemento
tam: tamaño del vector
dato: elemento que se quiere buscar.
Variables
centro: elemento central del intervalo
inf: límite inferior del intervalo
sup: límite superior del intervalo
inf = 0
sup = tam-1
Mientras inf <= sup:
centro = ((sup - inf) / 2) + inf //División entera: se trunca la parte decimal
Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:
Si dato < vec[centro] entonces:
sup=centro-1
En caso contrario:
inf=centro+1
Fin (Mientras)
Devolver Falso
"TRANSFORMACIÒN DE CLAVES"
Es un método de búsqueda que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento. Esta correspondencia se realiza mediante una función de conversión, llamada función hash. La correspondencia más sencilla es la identidad, esto es, al número 0 se le asigna el índice 0, al elemento 1 el índice 1, y así sucesivamente. Pero si los números a almacenar son demasiado grandes esta función es inservible. Por ejemplo, se quiere guardar en un array la información de los 1000 usuarios de una empresa, y se elige el núemro de DNI como elemento identificativo. Es inviable hacer un array de 100.000.000 elementos, sobre todo porque se desaprovecha demasiado espacio. Por eso, se realiza una transformación al número de DNI para que nos de un número menor, por ejemplo coger las 3 últimas cifras para guardar a los empleados en un array de 1000 elementos. Para buscar a uno de ellos, bastaría con realizar la transformación a su DNI y ver si está o no en el array.
La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar. La función de hash depende de cada problema y de cada finalidad, y se pueden utilizar con números o cadenas, pero las más utilizadas son:
Restas sucesivas: esta función se emplea con claves numéricas entre las que existen huecos de tamaño conocido, obteniéndose direcciones consecutivas. Por ejemplo, si el número de expediente de un alumno universitario está formado por el año de entrada en la universidad, seguido de un número identificativo de tres cifras, y suponiendo que entran un máximo de 400 alumnos al año, se le asignarían las claves: 1998–000 → 0 = 1998000–1998000 1998–001 → 1 = 1998001–1998000 1998–002 → 2 = 1998002–1998000
…
1998–399 → 399 = 1998399–1998000 1999–000 → 400 = 1999000–1998000+400
…
yyyy-nnn → N = yyyynnn-1998000+(400*(yyyy-1998))
Aritmética modular: el índice de un número es resto de la división de ese número entre un número N prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a N-1. Este método tiene el problema de que cuando hay N+1 elementos, al menos un índice es señalado por dos elementos (teorema del palomar). A este fenómeno se le llama colisión, y es tratado más adelante. Si el número N es el 13, los números siguientes quedan transformados en: 13000000 → 0 12345678 → 7 13602499 → 1 71140205 → 6 73062138 → 6
Mitad del cuadrado: consiste en elevar al cuadrado la clave y coger las cifras centrales. Este método también presenta problemas de colisión: 123*123=15129 → 51 136*136=18496 → 84 730*730=532900 → 29 301*301=90601 → 06 625*625=390625 → 06
Truncamiento: consiste en ignorar parte del número y utilizar los elementos restantes como índice. También se produce colisión. Por ejemplo, si un número de 8 cifras se debe ordenar en un array de 1000 elementos, se pueden coger la primer, la tercer y la última cifras para formar un nuevo número: 13000000 → 100 12345678 → 138 13602499 → 169 71140205 → 715 73162135 → 715
Plegamiento: consiste en dividir el número en diferentes partes, y operar con ellas (normalmente con suma o multiplicación). También se produce colisión. Por ejemplo, si dividimos los número de 8 cifras en 3, 3 y 2 cifras y se suman, dará otro número de tres cifras (y si no, se cogen las tres últimas cifras): 13000000 → 130=130+000+00 12345678 → 657=123+456+78 71140205 → 118 → 1118=711+402+05 13602499 → 259=136+024+99 25000009 → 259=250+000+09
Tratamiento de colisiones: Pero ahora se nos presenta el problema de qué hacer con las colisiones, qué pasa cuando a dos elementos diferentes les corresponde el mismo índice. Pues bien, hay tres posibles soluciones:
Cuando el índice correspondiente a un elemento ya está ocupada, se le asigna el primer índice libre a partir de esa posición. Este método es poco eficaz, porque al nuevo elemento se le asigna un índice que podrá estar ocupado por un elemento posterior a él, y la búsqueda se ralentiza, ya que no se sabe la posición exacta del elemento.
También se pueden reservar unos cuantos lugares al final del array para alojar a las colisiones. Este método también tiene un problema: ¿Cuánto espacio se debe reservar? Además, sigue la lentitud de búsqueda si el elemento a buscar es una colisión.
Lo más efectivo es, en vez de crear un array de número, crear un array de punteros, donde cada puntero señala el principio de una lista enlazada. Así, cada elemento que llega a un determinado índice se pone en el último lugar de la lista de ese índice. El tiempo de búsqueda se reduce considerablemente, y no hace falta poner restricciones al tamaño del array, ya que se pueden añadir nodos dinámicamente a la lista.
