BUSQUEDA

http://www.lcc.uma.es/~afdez/apuntes/metodologia/transparencias/eco_ordenacionbusqueda.PDF

Búsqueda Binaria

Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes: Los datos deben estar contenido en un estructura de datos tipo vector Los datos del vector deben estar ordenados  Una vez que se cuenten son las características descritas, se divide el vector para poder conocer la posición central y se verifica si es el dato que se esta buscando (lineas 9-12), si es el dato que se busca regresa la posición (índice del vector), en caso de que no sea el dato que buscamos se verifica si es mayor o menor que la posición central y se vuelve a redefinir la posición final o inicial según cumpla la condición (lineas 14-18). Debido a que el vector se encuentra ordenado si el dato que buscamos es mayor a la posición central se descartan todos los datos que se encuentren en la parte inferior, de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector. Una vez que encuentre el dato el método regresara la posición en que lo encontró (linea 12), en caso de no encontrar el dato en el vector regresara el valor -1 La implementación de este ejemplo del algoritmo de búsqueda binaria se encuentra en el lenguaje de programación Java.

Busqueda Secuencial

En este ocasion voy a explicar los algoritmos de busquedas secuenciales , este tipo de algoritmos nos facilita la forma de hacer consultas ya sea en una tabla de una base de datos como en un vector o matriz de datos (que al final viene siendo lo mismo que en una base de datos; xD ).

Este tipo de busqueda tiene mas puntos en contra que a favor porque en un vector de N posicioneseste algoritmo va a buscar posicion a posicion hasta dar con el dato solicitado y en el caso de que no exista pues tambien va a recorrer todo el arreglo.

Lo bueno de este tipo de busqueda es que es muy sencillo de implementar y no se tiene que ordenar el vector si tomamos el ejemplo anterior todavia como valido.

Bueno mucha explicacion vamos a la practica...

Si tenemos un vector ya definido con los siguientes datos:

["aarona","aashta","abelarda","abelia","abigail","a bril"] , todos de

tipo String y queremos saber si ya existe el nombre : "Abigail" en nuestro vector entonces tenemos que hacer lo siguiente:

public class BSecuencial {

public static void main(String[] args)throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ",
"Abril"};

System.out.print("Digite el nombre que desea buscar: ");
String nombre = entrada.readLine();
// entrada de dato a buscar

for (int i=0; i<VectorNombres.length;i++){

if(nombre.equalsIgnoreCase(VectorNombres[i])){

JOptionPane.showMessageDialog(null,"Elemento encontrado "+VectorNombres[i],"Encontrado",
JOptionPane.INFORMATION_MESSAGE);
encontrados++;
continue;
}


}

if(encontrados == 1 ){
System.out.println("Fin de busqueda, encontrado "+encontrados+" elemento igual");
}else{
System.out.println("Fin de busqueda, encontrados "+encontrados+" elementos iguales");
}


}

}

METODO DE BUSQUEDA HASHING

Hash: se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.

FUNCION HASH

Es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor. Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada
VENTAJAS:
Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar
Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones
No se requiere almacenamiento adicional para los índices.

DESVENTAJAS:

El archivo no esta clasificado
No permite llaves repetidas
Solo permite acceso por una sola llave
Costos
Tiempo de procesamiento requerido para la aplicación de la función hash

ALGORITMO HASHING

Algoritmo que se utiliza para generar un valor de hash para algún dato, como por ejemplo claves. Un algoritmo de hash hace que los cambios que se produzcan en los datos de entrada provoquen cambios en los bits del hash. Gracias a esto, los hash permiten detectar si un dato ha sido modificado.

ALGORITMOS DE HASH MAS COMUNES

SHA-1: algoritmo de hash seguro Algoritmo de síntesis que genera un hash de 160 bits. Se utiliza, por ejemplo, como algoritmo para la firma digital.
MD2 y MD4 Algoritmos de hash que generan un valor de 128 bits.
MD5 Esquema de hash de hash de 128 bits muy utilizado para autenticación cifrada. Gracias al MD5 se consigue, por ejemplo, que un usuario demuestre que conoce una contraseña sin necesidad de enviar la contraseña a través de la red.

FUNCIONES DE HASH

Residuo de la división
Medio del cuadrado
Pliegue
RESIDUO DE LA DIVISIÓN
La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).       Mientras que el valor calculado real de una dirección relativa, dados tanto un valor de llave como el divisor, es directo; la elección del divisor apropiado puede no ser tan simple. Existen varios factores que deben considerarse para seleccionar el divisor:
RESIDUO DE LA DIVISIÓN

El rango de valores que resultan de la operación "llave % divisor", va desde cero hasta el divisor 1. Luego, el divisor determina el tamaño del espacio de direcciones relativas. Si se sabe que el archivo va a contener por lo menos n registros, entonces tendremos que hacer que divisor > n, suponiendo que solamente un registro puede ser almacenado en una dirección relativa dada.
El divisor deberá seleccionarse de tal forma que la probabilidad de colisión sea minimizada. ¿Como escoger este numero? Mediante investigaciones se ha demostrado que los divisores que son números pares tienden a comportase pobremente, especialmente con los conjuntos de valores de llave que son predominantemente impares. Algunas investigaciones sugieren que el divisor deberá ser un numero primo. Sin embargo, otras sugieren que los divisores no primos trabajan también como los divisores primos, siempre y cuando los divisores no primos no contengan ningún factor primo menor de 20. Lo mas común es elegir el número primo mas próximo al total de direcciones.
RESIDUO DE LA DIVISIÓN

Ejemplo:      
Numero de direcciones 996. La eleccion de m sera 997, que es el primo mas cercano. Se aplica esta función hash cuyo número es:
245643
h(245643) = 245643 mod 997 = 381
MEDIO DEL CUADRADO 

En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n dígitos deben extraerse para cada llave.
MEDIO DEL CUADRADO 

RADIX

En informática, el ordenamiento Radix (radix sort en inglés) 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 entero.

La mayor parte de los ordenadores digitales representan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente. Existen dos clasificaciones de radix sort: el de dígito menos significativo (LSD) y el de dígito más significativo (MSD). 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.Descripción

Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos.Radix sort LSD usa típicamente el siguiente orden: claves cortas aparecen antes que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija. Una secuencia como "b, c, d, e, f, g, h, i, j, ba" será ordenada léxicamente como "b, ba, c, d, e, f, g, h, i, j". Si se usa orden léxico para ordenar representaciones de enteros de longitud variable, entonces la ordenación de las representaciones de los números del 1 al 10 será "1, 10, 2, 3, 4, 5, 6, 7, 8, 9", como si las claves más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con espacios en blanco, para hacerlas tan largas como la clave más larga, para el propósito de este ordenamiento.

ORDENAMIENTO

ORDENAMIENTO DE BURBUJA.

Concepto.

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. 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 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 el mé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.

Descripcion.

Una manera simple de expresar el ordenamiento de burbuja en pseudocódigo es la siguiente:

La burbuja son dos términos de la lista seguidos, j y j+1, que se comparan, si el primero es menor que el segundo sus valores se intercambian.Este algoritmo realiza el ordenamiento de una lista a de n valores, en este caso de n términos numerados del 0 aln-1, consta de dos bucles anidados uno con el índice i, que da un tamaño menor al recorrido de la burbuja en sentido inverso de 2 a n, y un segundo bucle con el índice j, con un recorrido desde 0 hasta n-i, para cada iteración del primer bucle, que indica el lugar de la burbuja.

Esta comparación se repite en el centro de los dos bucles, dando lugar a la postre a una lista ordenada, puede verse que el número de repeticiones sola depende de n, y no del orden de los términos, esto es, si pasamos al algoritmo una lista ya ordenada, realizara todas las comparaciones exactamente igual que para una lista no ordenada, esta es una característica de este algoritmo, luego veremos una variante que evita este inconveniente.

Ejemplo:

Tenemos una lista de números que hay que ordenar:

El índice i hará un recorrido de 2 hasta n:Podemos ver que la lista que tiene cinco términos, luego:

Que en este caso será de 2 a 5. Para cada uno de los valores de i, j tomara sucesivamente los valores de 0 hasta n-i:

Para cada valor de j, obtenido en ese orden, se compara el valor del índice j con el siguiente:

Para el caso del ejemplo, tenemos que:                                                      Si el termino j es menor, en su caso podría se mayor, que el termino j+1, los valores se permutan, en caso contrario se continúa con la iteración.

Para la primera iteración del primer bucle:

y j tomara los valores de 0 hasta 3:

Ahora j vale 1 y se comparan  el 86 y el 48 Como 86 > 48, se permutan, dando lugar a una nueva lista.Cuando j vale 0, se comparan , el 55 y el 86, dado que 55 < 86 no se permutan el orden.

Se repite el proceso hasta que j valga 3, dando lugar a una lista parcialmente ordenada, podemos ver que el termino de mayor valor esta en el lugar más alto.

Ahora i vale 3, y j hará un recorrido de 0 a 2.

Primero j vale 0, se comparan , el 55 y el 48, como 55 > 48 se permutan dando lugar a la nueva lista.

Para j = 1 se compara el 55 con el 16 y se cambian de orden.

El algoritmo consiste en comparaciones sucesivas de dos términos consecutivos, ascendiendo de abajo a arriba en cada iteración, como la ascensión de las burbujas de aire en el agua, de ahí el nombre del procedimiento, en la primera iteración el recorrido ha sido completo, en el segundo se ha dejado él último termino, al tener ya el mayor de los valores, en los sucesivos sé ira dejando de realizar las ultimas comparaciones, como se puede ver.Para j = 2 se compara el 55 y el 82 y se dejan como están, finalizando el bucle con una lista mejor ordenada, puede verse que los dos valores más altos ya ocupan su lugar. No se ha realizado ninguna comparación con el termino cuarto, dado que ya se sabe que después del primer ciclo es el mayor de la lista.

Ahora ya i vale 4 y j recorrerá los valores de 0 a 1.

Cuando j vale 0, se comparan  esto es el 48 y el 16 dado que 48 es mayor que 16 se permutan los valores, dando lugar a una lista algo más ordenada que la anterior, desde esta nueva ordenación, j pasa a valer 1, con lo que se comparan los términos  el 48 y el 55 que quedan en el mismo orden.

En este caso la burbuja ha ascendido menos que en los casos anteriores, y la lista esta ya ordenada, pero el algoritmo tendrá que completarse, realizando una ultima iteración.

Hay que tener en cuenta que el bucle para realiza un número fijo de repeticiones y para finalizar tendrán que completarse, aun en el caso extremo, de que la lista estaría previamente ordenada.

Los bucles finalizan y también el procedimiento, dejando la lista ordenada.Por último i vale 5 y j solo puede vale 0, con lo que solo se realizara una comparación de  el 16 y el 48, que ya están ordenados y se dejan igual.

Una variante que finaliza en caso de que la lista este ordenada, puede ser la siguiente, empleando un centinela ordenado, que detecta que no se ha modificado la lista en un recorrido de la burbuja, y que por tanto la lista ya esta ordenada, finalizando.

Programa.

01	public class DemoOrdenamiento

02

{

03	public static void main(String []args)

04

{

05	Ordenamiento datos=new Ordenamiento();

06	int sw,opcion;

07

08	datos.ingreso();

09

sw=1;

10

do{

11

12	System.out.println("0. Salir");

13	System.out.println("1. Burbuja Derecha Izquierda");

14	System.out.println("2. Burbuja de derecha a Izquierda");

15	System.out.println("3. Inserción Directa");

16	System.out.println("4. Selección Directa");

17	System.out.println("5. Metodo Shell");

18	System.out.println("6. Ordenamiento rápido");

19	System.out.print("Opcion ==> ");

20	opcion=Leer.datoInt();

21	if(opcion>0)

22

{

23	System.out.println("Arreglo antes de ordenar");

24	datos.reporte();

25

}

26

27	switch(opcion)

28

{

29	case 0: sw=0;break;

30	case 1: datos.burbuja_der_izq();break;

31	case 2: datos.burbuja_izq_der();break;

32	case 3: datos.baraja();break;

33	case 4: datos.seleccion_directa();break;

34	case 5: datos.shell();break;

35	case 6: datos.quicksort(datos.a,0,datos.n-1);break;

36

}

37

38	if(opcion>0)

39

{

40	System.out.println("Arreglo despues de ordenar");

41	datos.reporte();

42

}

43

44	}while(sw==1);

45

}

46

}

Video

ORDENAMIENTO QUICKSORT.

Concepto
Si bien el método de la burbuja era considerado como el peor método de ordenación simple o menos eficiente, el método Quicksort basa su estrategia en la idea intuitiva de que es más fácil ordenar una gran estructura de datos subdividiéndolas en otras más pequeñas introduciendo un orden relativo entre ellas. En otras palabras, si dividimos el array a ordenar en dos subarrays de forma que los elementos del subarray inferior sean más pequeños que los del subarray superior, y aplicamos el método reiteradamente, al final tendremos el array inicial totalmente ordenado. Existen además otros métodos conocidos, el de ordenación por montículo y el de shell.


Descripción del algoritmo
El algoritmo consta de los siguientes pasos:

·                     Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

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

·                     La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

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

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

·                     En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).

·                     En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

·                     En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Demostración de un caso particular

Supongamos que el número de elementos a ordenar es una potencia de dos, es decir, n = 2^k para algún natural k. Inmediatamente k = log₂(n), donde k es el número de divisiones que realizará el algoritmo.
En la primera fase del algoritmo habrá n comparaciones. En la segunda fase el algoritmo instanciará dos sublistas de tamaño aproximadamente n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.
En conclusión, el número total de comparaciones que hace el algoritmo es:
n + n + n + ..... + n = kn, donde k = log₂(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log₂n).

Técnicas de elección del pivote

El algoritmo básico del método Quicksort consiste en tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la partición en que se elija, el algoritmo será más o menos eficiente.

·                     Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista.

·                     Otra opción puede ser recorrer la lista para saber de antemanoqué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n·log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio.

·                     La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote.

Técnicas de reposicionamiento

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la recursividad.
Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:

·                     Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).

·                     Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones.

·                     Repetir esto hasta que se crucen los índices.

·                     El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados). 

Operaciones
   Las operaciones de ordenamiento con quicksort, son el de elegir un pivote, el cual va a ser las comparaciones, y asi poder hacer comparaciones, ya que al tener el pivote podremos saber al momento de hacer las comparaciones, si movemos a la izquierda o a la derecha.

Video

Programa.

Bibliografia
http://es.wikipedia.org/wiki/Quicksort
http://www.genbetadev.com/algoritmos/implementando-el-algoritmo-quicksort

ORDENAMIENTO SHELLSORT.

Shellsort

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;

Recorrido	Salto	Lista Ordenada	Intercambio
1	3	2,1,4,0,3,5,6	(6,2), (5,4), (6,0)
2	3	0,1,4,2,3,5,6	(2,0)
3	3	0,1,4,2,3,5,6	Ninguno
4	1	0,1,2,3,4,5,6	(4,2), (4,3)
5	1	0,1,2,3,4,5,6	Ninguno

video