ALGORITMICA IIIAlgoritmos de BsquedaDocente: Carlos A. Ruiz De La Cruz MeloCorreo: zorroculto69@hotmail.com

Los algoritmos de bsqueda tienen como finalidad localizar un elemento dado dentro de una estructura de datos o determinar su inexistencia.

Naturalmente, la bsqueda ser mucho ms eficiente si la estructura de datos (en nuestro caso el vector) est ordenada.

As, los algoritmos que estudiaremos servirn para realizar bsquedas en vectores ordenados.INSTRODUCCION

A lo largo de esta leccin estudiaremos los siguientes algoritmos de bsqueda:

Bsqueda secuencial.Bsqueda secuencial con centinela.Bsqueda binaria (o dicotmica)Bsqueda por interpolacin.

Se presentar pseudocdigo y anlisis de la complejidad para cada uno de los algoritmos.ALGORITMOS DE BUSQUEDA

El algoritmo de bsqueda ms sencillo recorre el vector desde el primer elemento hasta el ltimo y si encuentra el valor buscado retorna su posicin o avisa que lo encontro.

Obviamente, se trata del nico algoritmo posible si el vector no est ordenado.

Sin embargo, si el vector est ordenado resulta muy ineficiente.BUSQUEDA SECUENCIAL

BUSQUEDA SECUENCIALFuncion busquedaSecuencial(v, n, valor): lgico entero: i, n logico: encontro encontrofalso para i0 hasta n hacer si v(i)=valor entonces encontroverdadero fin si finpara retornar encontrofinbusquedaSecuencialComo se puede apreciar el algoritmo realiza siempre el mismo nmero de iteraciones independientemente de la posicin en que se encuentre el valor buscado.

El nmero de iteraciones siempre es igual al tamao del vector y, puesto que todas las operaciones del interior del bucle tienen coste unitario, la complejidad del algoritmo de bsqueda secuencial es O(n).

El algoritmo de bsqueda secuencial resulta muy ineficiente puesto que no se aprovecha del hecho de que el vector est ordenado.

Es posible modificarlo para que, teniendo en cuenta esa circunstancia, finalice en cuanto localice el elemento o se determine que ste no existe.

Esta modificacin se conoce como bsqueda secuencial con centinela.BUSQUEDA SECUENCIAL CON CENTINELAFuncion BusSecSentinela(v, n, valor):logicoi0mientras v(i)

La bsqueda secuencial con centinela no precisa recorrer el vector por completo.

El caso mejor se produce cuando el elemento a buscar es el primero del vector o menor que todos los elementos del vector. Entonces la complejidad es O(1).

El caso peor se da cuando el elemento a buscar es el ltimo del vector o mayor que todos los elementos del vector. Entonces la complejidad es O(n).

Por trmino medio, el algoritmo emplea del orden de n/2 iteraciones, por lo cual la complejidad del caso medio tambin sera O(n).BUSQUEDA SECUENCIAL CON CENTINELAFuncion BusSecSentinela(v, n, valor):logicoi0mientras v(i)

La idea bsica de la bsqueda binaria o dicotmica es reducir el tamao del problema a la mitad en cada iteracin.

Cuando el tamao del problema, esto es del vector, sea 1 se puede resolver la bsqueda de forma directa.

La estrategia empleada por este algoritmo es muy similar a la del juego patata caliente...BUSQUEDA BINARIA

Funcion BusquedaBinaria(v, valor): enteroposicion-1encontradofalsoizq1derMAXmientras no encontrado y izq der hacer medio(izq+der)/2 Si v(medio)=valor entonces posicionmedio encontradoverdadero sino si v(medio)>valor entonces dermedio-1 sino izqmedio+1 finsi finsi fin mientras busquedaBinariaposicionfin funcionBUSQUEDA BINARIA

BUSQUEDA BINARIAEn el vector (1,1,2,3,4,5,5,5,6,9) se va a buscar, de forma binaria, el nmero 7

Observacin

que bastan 4 iteraciones para determinar que el nmero 7 no se encuentra en el vector.

El algoritmo de bsqueda binaria divide el tamao del vector por 2 hasta quedarse con un vector de tamao 1.

Al llegar al tamao unitario se puede determinar directamente si el elemento buscado existe o no.

As, el algoritmo de bsqueda binaria realiza log2(n) iteraciones y, por tanto, su complejidad es O(log n).BUSQUEDA BINARIAFuncion BusquedaBinaria(v, valor): enteroposicion-1encontradofalsoizq1derMAXmientras no encontrado y izq der hacer medio(izq+der)/2 Si v(medio)=valor entonces posicionmedio encontradoverdadero sino si v(medio)>valor entonces dermedio-1 sino izqmedio+1 finsi finsi fin mientras busquedaBinariaposicionfin funcion

Consiste en tratar de acertar en qu parte del intervalo est la clave que se esta buscando en lugar de ciegamente dividir el arreglo a la mitad. Para ello se utiliza la siguiente frmula:

BUSQUEDA POR INTERPOLACION

funcion busquedaInterpolacion (v,valor) :entero entero: v(max), valor entero: izq,der, presunto, busqueda izq1 dermax mientras ((v[der] valor) y (v[izq] < valor)) pizq+(valor-v[izq])*(der - izq) /(v[der]-v[izq]) si (valor > v[p]) entonces izqp+1 sino si (valor < v[p]) entonces derp-1 sino izqp finsi finsi finmientras si (v[izq]=valor) then busquedaizq sino busqueda -1 finsi retornar busquedafinBusquedaDeInterpolacion BUSQUEDA POR INTERPOLACION

BUSQUEDA POR INTERPOLACIONLa bsqueda por interpolacin utiliza menos de log log n +1 comparaciones tanto para una bsqueda con xito como para una bsqueda infructuosa en archivos con claves aleatorias.

Depende fuertemente de que las claves estn bien distribuidas en el intervalo. Esta tcnica puede ser engaada' una distribucin no uniforme (lo que es frecuente en la prctica). Los clculos requeridos no merecen la pena si n es pequeo (log n log log n ).

La bsqueda es una de las operaciones de tratamiento de vectores ms habituales.

Una bsqueda en un vector no ordenado tendra una complejidad O(n); por esa razn es preferible implementar algoritmos de bsqueda en vectores ordenados.

Hemos estudiado 4 algoritmos de bsqueda:

Bsqueda secuencial.Bsqueda secuencial con centinela.Bsqueda binaria.Bsqueda por interpolacin.

CONCLUSIONES DE BUSQUEDA

El primer algoritmo es el ms simple de los cuatro, recorre completamente el vector y no precisa que el vector es ordenado; su complejidad es O(n).

El segundo algoritmo recorre el vector hasta que se encuentra el valor buscado o se determina que ste no existe. Su complejidad es O(n).

El algoritmo de bsqueda binaria divide en cada iteracin el vector en dos realizando la bsqueda en una sola de las mitades. Su complejidad es O(log n).

La bsqueda por interpolacin es una modificacin del algoritmo de bsqueda binaria, tambin de complejidad O(log n).CONCLUSIONES DE BUSQUEDA

ALGORITMICA IIIAlgoritmos de ClasificacinDocente: Carlos A. Ruiz De La Cruz MeloCorreo: zorroculto69@hotmail.com

INTRODUCCINSea A una lista de N elementos:

A1, A2, A3, ..., An

Se busca permutar estos elementos de tal forma que los mismos queden de acuerdo con un orden preestablecido.

Ascendente: A1 A2 A3 ... An

Descendente: A1 A2 A3 ... An

INTRODUCCINAunque tanto el tipo y tamao de los elementos como el dispositivo en donde se encuentran almacenados pueden influir en el mtodo que utilicemos para ordenarlos, en este tema vamos a solucionar el caso en que los elementos son nmeros enteros y se encuentran almacenados en un vector.

Si bien existen distintos criterios para clasificar a los algoritmos de ordenacin, una posibilidad es atendiendo a su eficiencia. De esta forma, en funcin de la complejidad que presentan en el caso medio, podemos establecer la siguiente clasificacin:(n 2): Burbuja, Insercin, Seleccin.(nlogn): Mezcla, Quicksort.Otros: Shell (n1.25).

CLASIFICACIN POR SELECCINConsiste bsicamente en buscar el menor elemento del arreglo y colocarlo al inicio.

Luego buscar el segundo elemento ms pequeo del arreglo y colocarlo en la segunda posicin,

Y as hasta ubicar todos los elementos del arreglo.

La insercin de un elemento posterior requerir que se muevan muchos de ellos.algoritmo seleccin(a, n) para i1 hasta n-1 hacer menora[i] ki para ji+1 hasta n si a[j]

Deseamos ordenar las siguientes claves de arreglo:L: 15 67 08 16 44 27 12 35CLASIFICACIN POR SELECCINEn cada paso (i=1...n1) este mtodo busca el mnimo elemento del subvector a[i..n] y lo intercambia con el elemento en la posicin i:

CLASIFICACIN POR SELECCINEn el caso mejor:algoritmo seleccin(a, n) para i1 hasta n-1 hacer menora[i] ki para ji+1 hasta n si a[j]

CLASIFICACIN POR SELECCINalgoritmo seleccin(a, n) para i1 hasta n-1 hacer menora[i] ki para ji+1 hasta n si a[j]

CLASIFICACIN POR SELECCINalgoritmo seleccin(a, n) para i1 hasta n-1 hacer menora[i] ki para ji+1 hasta n si a[j]

CLASIFICACIN POR SELECCINEl algoritmo es de complejidad cuadrtica.

Este mtodo, por el nmero de operaciones de comparacin e intercambio que realiza, es el ms adecuado para ordenar pocos registros de gran tamao.

algoritmo seleccin(a, n) para i1 hasta n-1 hacer menora[i] ki para ji+1 hasta n si a[j]

El nmero de comparaciones es independiente de la disposicin inicial de los elementos en el arreglo.

En la primera pasada se hacen (n-1) comparaciones, en la siguiente (n-2) y as hasta 1 en la ltima pasada.

El nmero de movimientos siempre ser n-1 (salvo que se incorpore al algoritmo una tcnica para evitar que un elemento se intercambie consigo mismo).algoritmo seleccin(a, n) para i1 hasta n-1 hacer menora[i] ki para ji+1 hasta n si a[j]

Ejemplo:Arreglo con elementos: 15 67 08 16 44 27 12 35CLASIFICACIN POR INTERCAMBIO

CLASIFICACIN POR INTERCAMBIOEs el mtodo ms ineficiente, tambin llamado burbuja.

Lleva los elementos pequeos hacia la parte izquierda del arreglo o bienLleva los elementos ms grandes hacia la parte derecha del mismo.

Compara pares de elementos adyacentes e intercambiarlos entre s hasta que todos se encuentren ordenados.

Por lo tanto en cada pasada se ordenar un elemento.

algoritmo burbuja(a, n) para i1 hasta n-1 hacer para jn hasta i+1 por -1 hacer si a[ j-1]> a[ j ] entonces auxa[j-1] a[ j-1]a[ j ] a[ j ]aux finsi finpara finpara finburbuja

CLASIFICACIN POR INTERCAMBIOEn el caso mejor:algoritmo burbuja(a, n) para i1 hasta n-1 hacer para jn hasta i+1 por -1 hacer si a[ j-1]> a[ j ] entonces auxa[j-1] a[ j-1]a[ j ] a[ j ]aux finsi finpara finpara finburbuja

CLASIFICACIN POR INTERCAMBIOEn el peor caso:algoritmo burbuja(a, n) para i1 hasta n-1 hacer para jn hasta i+1 por -1 hacer si a[ j-1]> a[ j ] entonces auxa[j-1] a[ j-1]a[ j ] a[ j ]aux finsi finpara finpara finburbuja

CLASIFICACIN POR INTERCAMBIOEn el caso medio:algoritmo burbuja(a, n) para i1 hasta n-1 hacer para jn hasta i+1 por -1 hacer si a[ j-1]> a[ j ] entonces auxa[j-1] a[ j-1]a[ j ] a[ j ]aux finsi finpara finpara finburbuja

CLASIFICACIN POR INTERCAMBIOEl algoritmo es de complejidad cuadrtica.

Este algoritmo funciona de forma parecida al de Seleccin, pero haciendo ms trabajo para llevar cada elemento a su posicin.

De hecho es el peor algoritmo de clasificacin, no slo en cuanto al tiempo de ejecucin, sino tambin respecto al nmero de comparaciones y de intercambios que realiza.

Una posible mejora que puede admitir este algoritmo es el control de la existencia de una pasada sin intercambios; en ese momento el vector estar ordenado.algoritmo burbuja(a, n) para i1 hasta n-1 hacer para jn hasta i+1 por -1 hacer si a[ j-1]> a[ j ] entonces auxa[j-1] a[ j-1]a[ j ] a[ j ]aux finsi finpara finpara finburbuja

El numero de comparaciones en el mtodo burbuja para n elementos es la siguiente:

En la primera pasada: n-1 comparacionesEn la segunda (n-2) comparaciones

Hasta llegar a 2 y 1 comparacinalgoritmo burbuja(a, n) para i1 hasta n-1 hacer para jn hasta i+1 por -1 hacer si a[ j-1]> a[ j ] entonces auxa[j-1] a[ j-1]a[ j ] a[ j ]aux finsi finpara finpara finburbujaCLASIFICACIN POR INTERCAMBIO

Ejemplo:Arreglo con elementos: 15 67 08 16 44 27 12 35CLASIFICACIN POR INSERCIN

CLASIFICACIN POR INSERCINEl mtodo de Insercin realiza n1 iteraciones sobre el vector, dejando en la isima etapa (2 i n) ordenado el subvector a[1..i].

La forma de hacerlo es colocando en cada iteracin el elemento a[i] en su sitio correcto, aprovechando el hecho de que el subvector a[1..i1] ya ha sido previamente ordenado.

Este mtodo puede ser implementado de forma iterativa como sigue:algoritmo insercion(a, n) para i2 hasta n xa[i] ji-1 mientras (j1) y (x

CLASIFICACIN POR INSERCINEn el caso mejor el bucle interno no se realiza nunca, y por tanto:algoritmo insercion(a, n) para i2 hasta n xa[i] ji-1 mientras (j1) y (x

En el caso peor hay que llevar cada elemento hasta su posicin final, con lo que el bucle interno se realiza siempre de i1 veces. As, en este caso:CLASIFICACIN POR INSERCINalgoritmo insercion(a, n) para i2 hasta n xa[i] ji-1 mientras (j1) y (x

CLASIFICACIN POR INSERCINEn el caso medio, supondremos equiprobable la posicin de cada elemento dentro del vector.

Por tanto para cada valor de i, la probabilidad de que el elemento se site en alguna posicin k de las i primeras ser de 1/i.

El nmero de veces que se repetir el bucle mientras en este caso es (ik), con lo cual el nmero medio de operaciones que se realizan en el bucle es:algoritmo insercion(a, n) para i2 hasta n xa[i] ji-1 mientras (j1) y (x

Por tanto, el tiempo de ejecucin en el caso medio es:CLASIFICACIN POR INSERCINalgoritmo insercion(a, n) para i2 hasta n xa[i] ji-1 mientras (j1) y (x

Como podemos ver, en este mtodo los rdenes de complejidad de los casos peor, mejor y medio difieren bastante.

As en el mejor caso el orden de complejidad resulta ser lineal, mientras que en los casos peor y medio su complejidad es cuadrtica.

Este mtodo se muestra muy adecuado para aquellas situaciones en donde necesitamos ordenar un vector del que ya conocemos que est casi ordenado, como suele suceder en aquellas aplicaciones de insercin de elementos en bancos de datos previamente ordenados cuya ordenacin total se realiza peridicamente.CLASIFICACIN POR INSERCINalgoritmo insercion(a, n) para i2 hasta n xa[i] ji-1 mientras (j1) y (x

El nmero mnimo de comparaciones y movimientos entre claves sucede cuando los elementos ya est ordenados.

El nmero mximo de comparaciones y movimientos entre elementos se da cuando los elementos del arreglo estn en orden inverso.

El nmero de comparaciones promedio se da cuando los elementos aparecen en el arreglo de forma aleatoria.CLASIFICACIN POR INSERCINalgoritmo insercion(a, n) para i2 hasta n xa[i] ji-1 mientras (j1) y (x

CLASIFICACIN POR SHELLEl mtodo de Shell es una versin mejorada del mtodo de insercin directa.

Lo propuso Donald L. Shell en 1959.

Tambin se le conoce como clasificacin por disminucin del incremento.

Propone que las comparaciones entre elementos se efecten con saltos de mayor tamao pero con incrementos decrecientes para que los elementos queden ordenados ms rpidamente.algoritmo SHELL(a, ult)entero: i,j,h,NN(ult-prim+1) (* numero de elementos *)h1REPETIR h3*h+1 HASTA h>N (* construimos la secuencia *)REPETIR hh DIV 3 para ih+1 hasta N hacer va[i] ji mientras (j>h) y (a[j-h+prim-1]>v) hacer a[j+prim-1]a[j-h+prim-1] jj-1 hh-1 finmientras a[j+prim-1]v finparaHASTA h=1finSHELLObservacin: se sale de REPETIR ..HASTA cuando la condicin es verdadera

Imaginemos un arreglo de 16 elementos.

Se dividen los elementos en ocho grupos teniendo en cuenta los elementos a ocho posiciones de distancia entre s y se ordenan por separado.

Luego se dividen en cuatro grupos, teniendo en cuenta los elementos que se encuentren a cuatro posiciones entre s, y se les ordena por separado.

Se dividen en grupos tomando en cuenta los que se encuentran a dos porciones entre s y nuevamente se les ordena por separado.

Finalmente se agrupan y ordenan de manera normal, de uno en uno.algoritmo SHELL(a, ult)entero: i,j,h,NN(ult-prim+1) (* numero de elementos *)h1REPETIR h3*h+1 HASTA h>N (* construimos la secuencia *)REPETIR hh DIV 3 para ih+1 hasta N hacer va[i] ji mientras (j>h) y (a[j-h+prim-1]>v) hacer a[j+prim-1]a[j-h+prim-1] jj-1 hh-1 finmientras a[j+prim-1]v finparaHASTA h=1finSHELLCLASIFICACIN POR SHELL

Ej: Suponemos que se desea ordenar: L: 15 67 08 16 44 27 12 35 56 21 13 28 60 36 07 10CLASIFICACIN POR SHELL

CLASIFICACIN POR SHELL

Su complejidad es difcil de calcular y depende mucho de la secuencia de incrementos que utilice

En 1969 Pratt descubri que el tiempo de ejecucin del algoritmo es del orden n*(log n)2.

Se han efectuado estudios empricos sumamente amplios y al parecer, cuando n es grande, el nmero de movimientos flucta entre n5/4 y 1.6n5/4.

En general este mtodo es el escogido para muchas aplicaciones reales por ser muy simple teniendo un tiempo de ejecucin aceptable incluso para grandes valores de n.CLASIFICACIN POR SHELLalgoritmo SHELL(a, ult)entero: i,j,h,NN(ult-prim+1) (* numero de elementos *)h1REPETIR h3*h+1 HASTA h>N (* construimos la secuencia *)REPETIR hh DIV 3 para ih+1 hasta N hacer va[i] ji mientras (j>h) y (a[j-h+prim-1]>v) hacer a[j+prim-1]a[j-h+prim-1] jj-1 hh-1 finmientras a[j+prim-1]v finparaHASTA h=1finSHELL

CLASIFICACIN POR QUICKSORTEste mtodo es el ms eficiente y veloz de los mtodos de clasificacin.

Conocido como clasificacin rpida y clasificacin por particin.

La idea del algoritmo es la siguiente:

Se toma un elemento X de una posicin cualquiera del arreglo.Se trata de ubicar X en la posicin correcta del arreglo.Se repiten los pasos pero ahora con los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posicin correcta de X en el arreglo.El proceso termina cuando todos los elementos se encuentran en su posicin correcta en el arreglo.

Sea lo que deseamos clasificar. 15 67 08 16 44 27 12 35 Se selecciona L[1] = 15 = X y se compara con los siguientes: Recorremos de derecha a izquierda

X

Sea lo que deseamos clasificar. 15 67 08 16 44 27 12 35 CLASIFICACIN POR QUICKSORT

En el mejor caso, se escoge el elemento de la posicin central del conjunto de datos para analizar.

Respecto al nmero de comparaciones, el tamao del arreglo es de potencia de 2.

El peor caso ocurre cuando los elementos ya estn ordenados o los mismos se encuentran en orden inverso.

Pues al seleccionar el primer elemento se particionar el arreglo en dos nuevos conjuntos de 0 y (n-1) elementos.

CLASIFICACIN POR QUICKSORT

Anlisis de la Clasificacin por QuicksortDiversos estudios realizados sobre su comportamiento demuestran que si se escoge en cada pasada el elemento que ocupa la posicin central del conjunto de datos a analizar , el numero de pasadas necesarias para ordenarlo es del orden logn.

Respecto al numero de comparaciones si el tamao del arreglo es de potencia de 2 , en la primera pasada ser (n-1) comparaciones, en la segunda ser (n-1)/2, pero en dos conjuntos diferentes, en la tercera pasada realizara (n-1)/4 comparaciones, pero en cuatro conjuntos diferentes:

Anlisis de la Clasificacin por QuicksortSi el numero de trminos de la sumatoria es igual a m:Considerando que el numero de trminos de la sumatoria es igual al numero de pasadas y que este es igual a log n la expresin queda:

CLASIFICACIN POR MEZCLA DIRECTAConsiste en la realizacin sucesiva de una particin y una fusin que produce secuencias ordenadas de longitud 1

Y la fusin o mezcla produce secuencias ordenadas de longitud 2.

En la segunda pasada la particin es de longitud 2

Y la fusin o mezcla produce secuencias ordenadas de longitud 4.

Hasta que la longitud de la secuencia para la particin sea mayor o igual que el nmero de elementos del archivo original.

Ejemplo.

Desea ordenar las claves del arreglo F. Se usan dos arreglos auxiliares F1 y F2.

F: 09 75 14 68 29 17 31 25 04 05 13 18 72 46 61

Primera Pasada:

F1: 09 14 29 31 04 13 72 61 F2: 75 68 17 25 05 18 46

Fusin en secuencias de longitud 2.F: 09 75 14 68 17 29 25 31 04 05 13 18 46 72 61CLASIFICACIN POR MEZCLA DIRECTA

Segunda Pasada:Particin en secuencias de longitud 2.F1: 09 75 17 29 04 05 46 72F2: 14 68 25 31 13 18 61

Fusin en secuencias de longitud 4.F: 09 14 68 75 17 25 29 31 04 05 13 18 46 61 72

Tercera Pasada:Particin en secuencias de longitud 4.F1: 09 14 68 75 04 05 13 18F2: 17 25 29 31 46 61 72

Fusin en secuencias de longitud 8.F: 09 14 17 25 29 31 68 75 04 05 13 18 46 61 72CLASIFICACIN POR MEZCLA DIRECTA

Cuarta Pasada:Particin en secuencias de longitud 8.F1: 09 14 17 25 29 31 68 75F2: 04 05 13 18 46 61 72

Fusin en secuencias de longitud 16.F: 04 05 09 13 14 17 18 25 29 31 46 61 68 72 75 CLASIFICACIN POR MEZCLA DIRECTA

LaboratorioImplementando los siguientes algoritmos de clasificacin en java o C++, en arreglos:

SeleccinInsercionShellQuicksort

Pruebe todos ellos con la misma entrada (n) y evalu la diferencia en el numero de comparaciones e intercambios que realiza para ordenar el conjunto de datos.

Pruebe luego para todos ellos con diferentes tamaos de entrada(n) y aprecie la evolucin del tiempo de ordenacin con respecto al numero de datos a ordenar. Haga una grafica.