capítulo 7 busqueda y ordenamiento

Captulo 7.

http://sai.uam.mx/apoyodidactico/pa/Unidad7/pauni7.html[03/03/2010 11:54:38 a.m.]

Captulo 7.

1. Mtodos de bsqueda yordenamiento.

Dos de los problemas mas comunes en programacin, son los de bsqueda y ordenamiento. Son tan frecuentes, que existen varios mtodospara implementarlos.

1. Orden del mtodo

Como veremos existe mas de un mtodo tanto de bsqueda como de ordenamiento. Para poder decir que un mtodo es mejor o peor que otro,debemos de decir en que es mejor o peor. Normalmente los parmetros de comparacin son lgicamente el tiempo y la memoria que requieranlos mtodos. El principal desde el punto de vista del usuario es el tiempo. El tiempo de ejecucin de un programa que implemente algnmtodo de bsqueda u ordenamiento. depende de varios factores:

Los datos de entrada del programa.La calidad del cdigo escrito por el programador.La calidad del cdigo ejecutable generado por el compilador.La computadora que se utilice para correr el programa.La rapidez del algoritmo en si.

Es muy complicado evaluar matemticamente en una expresin todos estos factores. De ellos los mas relevantes son el tamao de los datos deentrada y la rapidez del algoritmo en si. El tamao de la entrada comnmente se representa por n, la rapidez del algoritmo se representa poralguna funcin matemtica f(n). El efecto de los dems factores se engloba en una constante k. Todo se expresa con la siguiente ecuacin:

Esta ecuacin nos expresa el tiempo de ejecucin. Como en general es complejo evaluar la constante, esta no se evala y solo nosconcentramos en f(n).

Existen 3 tiempos que se pueden considerar al evaluar el tiempo de ejecucin:

El tiempo del mejor caso.El tiempo del caso promedio.El tiempo del peor caso.

El primer tiempo se refiere a que se supone que todo es ideal. Por ejemplo si vamos a ordenar los datos de entrada, estos ya estn ordenados. Elsegundo caso se refiere al caso que con mayor frecuencia se presente. Por ejemplo en el caso de ordenamiento que los datos estndesordenados. El ultimo tiempo considera que lo peor puede ocurrir. Por ejemplo en el ordenamiento que los datos estn ordenados al revs decomo los deseamos. Usualmente son mas significativos los tiempos del peor caso y el tiempo promedio.

El tiempo del peor caso se denota usualmente como O(f(n)) y se lee como o mayscula de f(n) u orden del mtodo. El tiempo del mejor caso

se denota como y se como omega mayscula. Esta obviamente no es uy til. El tiempo del caso promedio simplemente lodenotaremos por T(n)=f(n).

Cuando comparemos algoritmos nos concentraremos en los ordenes, y cuando sea prudente en el tiempo del caso promedio.

La funcin f(n) puede ser de varios tipos, algunos frecuentes son:

f(n)=1. Constante.

Captulo 7.


f(n)=n. Lineal.f(n)=n2. Cuadrtico.f(n)=nm. Polinomial de grado m.f(n)=log n. Logartmico.f(n)=n log n.f(n)=2n. Exponencial de base 2.f(n)=mn. Exponencial de base m.

El mejor algoritmo ser aquel cuyo tiempo de ejecucin crezca mas lentamente. De las funciones anteriores los mejores son: constante,logartmicos, polinomial de grado m. Las peores son: exponencial de base m, polinomial de grado m.

1. Mtodos de bsqueda

La bsqueda de informacin es una tarea rutinaria. La informacin puede estar almacenada ya sea en memoria principal o en secundaria. Elproblema consiste en hallar un registro particular de entre todos los existentes. Nos restringiremos por simplicidad solo al caso de que lainformacin se halle en memoria principal. En este caso la informacin la almacenaremos en un arreglo.

El buscar un elemento especifico de un arreglo es una tarea comn. El problema puede plantearse de 2 maneras:

Saber si un elemento particular esta o no en el arreglo.Conocer la posicion del elemento de inters en el arreglo.

El segundo planteamiento es de mayor aplicacin y es el que seguiremos. En este caso si el elemento no esta nuestros algoritmos deben deindicarlo regresando una posicion invalida. Los algoritmos pueden implementarse ya sea con arreglos propiamente dicho o con apuntadores.En el primer caso si el elemento que buscamos no se halla, el algoritmo regresara -1. Para el caso de apuntadores regresaremos el apuntadorNULL.

Para realizar la bsqueda tenemos 2 casos:

Arreglo desordenado.Arreglo ordenado.

Para el primer caso el nico algoritmo disponible ser el de bsqueda secuencial. Para el segundo caso consideraremos el mtodo de bsquedabinaria.

1. Bsqueda secuencial

La bsqueda lineal o secuencial es la tcnica ms simple para buscar en un arreglo de datos. Este mtodo consiste en examinar todos loselementos de uno en uno, comenzando por el primer elemento del arreglo y comparando con el elemento buscado. El algoritmo prosigue hastahallarlo o llegar al final del arreglo. Consideraremos que se dispone de un vector x de n elementos y deseamos saber si el elemento e seencuentra en el vector y en caso afirmativo deducir la posicin del mismo en el vector. Con el fin de escribir el cdigo lo mas general posibleconsideraremos lo siguiente:

El tipo del arreglo lo definiremos con typedef denominndole tipo.La comparacin de los datos la haremos va un apuntador a funcin.El elemento NULO lo definiremos con una macro.

La posicin se representara con una variable POSICIN, que recibir el valor de la variable ndice del ciclo.

#define NULO -1

typedef |_| tipo;

int Bussec(tipo * x, int n, tipo e, int (* compara)(tipo, tipo))

{

int posicion=NULO;

for( i = 0; i< n; ++i)

if(!(* compara)(x[ i ],e)

Captulo 7.


posicion = i;

return (posicion);

}

El apuntador a funcin compara recibe la funcin usada para comparar los datos. La comparacin de datos depende fuertemente del tipo. Serequiere escribir una funcin que compare los datos tomando en cuenta su tipo. Esta funcin debe de funcionar igual que strcmp, es decir,regresa 0 si son iguales, un positivo si el primer parmetro es mayor al segundo o un negativo en caso contrario.

El procedimiento de bsqueda lineal se puede hacer un poco ms efectivo deteniendo el proceso una vez que se encuentre el elemento que seest buscando. Para realizar este nuevo algoritmo es necesario sustituir el ciclo for con un ciclo while o do while que nos permita salir del ciclouna vez que el dato ha sido encontrado.

Una bsqueda lineal es slo adecuada para arreglos cortos de datos.

El orden de este algoritmo es:

es decir, este algoritmo es de orden lineal. El tiempo de bsqueda es directamente proporcional al numero de datos.

En el caso promedio tenemos:

Un mtodo muy eficaz para buscar un elemento en una lista ordenada se denomina bsqueda binaria y se basa en el algoritmo de divisionessucesivas en mitades del diccionario comentado anteriormente.

1. Bsqueda binaria

El mtodo de bsqueda binaria utiliza el sistema de "divide y vencers" para localizar el elemento deseado. Supongamos un vector ordenadode elementos numricos

x[ 0 ] , x[ 1 ] ,...., x [ n-1]

en el que desea buscar el elemento e. Los pasos a seguir son:

1. Verificar si e < x[0] o bien e > x [n-1]. En este caso se ha terminado la bsqueda ya que el estar ordenado el vector x, se supone que eno existe en el vector.

Captulo 7.


2. Si e no cumple las condiciones anteriores, entonces e se encuentra en el vector y se calcula el elemento central de x, que se supone x[k]

x[ 0 ] , x[ 1 ] ,..., x[k],...,x [ n-1]

x[k]: elemento central

1. Se compara x[k] con e y pueden suceder tres casos:

1. e = x[k] el elemento se ha encontrado2. e < x[k] la bsqueda contina3. e > x[k] la bsqueda contina

1. En el caso II solamente se deber buscar en el subvector

x[ 0 ] , x[ 1 ] ,..., x[k-1]

mientras que el caso III se deber busca en el subvector

x[k+ 1 ] ,...,x [ n-1]

En ambos casos se ha dividido por dos la cantidad de datos donde se debe buscar.

1. En las listas compuestas por los subvectores se debern repetir de nuevo los pasos 1, 2, 3 y 4 hasta obtener un elemento x[i]=e, oconcluir que el elemento no esta.

Este mtodo se denomina bsqueda binaria debido a que se divide por dos el rango de la bsqueda. Mientras que en la bsqueda lineal senecesitan en el caso promedio ( n + 1 ) / 2 comparaciones, la bsqueda binaria emplea alrededor de log n comparaciones. Si n = 1000, n/2 =500, mientras que log2 1000 = 10. Escribiremos una funcin de bsqueda binaria que permita localizar un valor especificado en un arreglo yque devuelva el subndice del arreglo cuando se encuentra el valor. Si el valor no est almacenado en el arreglo se devolver -1.

int BusquedaBin (tipo * x, int n, tipo e, int (* compara)(tipo, tipo))

{

int primero=0, ultimo=n-1, central=(primero+ultimo)/2;

while(primero < = ultimo) {

if(!(* compara)(x[ central,e))

return (central);

else if((* compara)(x[ central,e)>0)

ultimo = central-1;

else

primero = central +1;

central=(primero+ultimo)/2;

}

return NULO;

Captulo 7.


}

1. Algoritmos de ordenamiento

El ordenamiento es una parte importante del manejo de informacin. Como ya mencionamos en los algoritmos de bsqueda, es mas eficienterealizar bsquedas si el arreglo esta ordenado que si no. Existen muchos algoritmos para ordenar. Veremos solo algunos.

1. Ordenamiento por insercin

El mtodo de ordenamiento por insercin es utilizado por los jugadores de cartas o naipes para ordenar sus barajas. Para desarrollar elalgoritmo imaginemos que las cartas se encuentran situadas en una hilera encima de la mesa; a medida que se ve una nueva carta, sta secompara con la hilera, carta por carta hasta hallar su posicion correspondiente, se debe empujar alguna de ellas a la derecha para dejar espacioe insertar la nueva, en su posicion. Escribiremos la funcin de ordenacin por insercin de un vector de n elementos.

void Insercion(tipo * x, int n, int (* compara)(tipo, tipo))

{

int quien,conquien,adonde;

tipo aux;

for (quien = 1; quien

Captulo 7.


copia(&x[i+1],&x[i]); /* Copiar en la posicion siguiente */

}

La funcin busec realiza una bsqueda secuencial de la posicion que le corresponde al elemento actual.

La copia de un elemento en otro depende del tipo de dato. La funcin copia realiza esto. Debe de escribirse para cada aplicacin.

La funcin recorre mueva los elementos del arreglo para hacer espacio y poder insertar el elemento actual.

El orden y el tiempo del caso promedio de este mtodo es :

1. Ordenamiento por burbuja o intercambio

El mtodo de la burbuja es uno de los ms conocidos por su sencillez y facilidad de implementacin. La idea bsica del mtodo es compararelementos consecutivos en cada paso a lo largo del vector. Cada vez que se realiza una comparacin los elementos se intercambian entre si encaso de no estar en orden. Es decir, se examinan dos elementos adyacentes X[i] y X[i + 1]; en caso de no estar ordenados

X[ i ] < X[ i + 1 ] o bien X[ i ] > X[ i + 1 ]

se intercambian los valores de dichos elementos.

El mtodo comienza comparando X[0] con X[ 1 ] y se intercambian si es necesario. A continuacin se compara X[0] con X[2] y seintercambian si es necesario, y as sucesivamente. Despus el procedimiento se repite con X[1], despus con x[2], etc. Despus de cadacomparacin, se intercambian los dos valores si no estn en el orden deseado. A este mtodo se le conoce con el nombre de la burbuja, porqueen el ordenamiento los elementos ms ligeros suben en la lista como burbujas a la superficie del lquido.

El algoritmo correspondiente es:

void Burbuja(tipo * x, int n, int (* compara)(tipo, tipo)))

{

int quien, conquien;

for (quien=0; quien

Captulo 7.


*H2O=*leche;

*leche=vaso;

}

El ndice quien nos indica a quien vamos a comparar y conquien nos indica con que elemento lo vamos a comparar.

La funcin intercambia realiza el intercambio de los valores, de los elementos del arreglo.

El orden y el tiempo del caso promedio de este mtodo es :

1. Ordenacin rpida

Posiblemente el algoritmo mas popular para el ordenamiento sea el de ordenacin rpida. La idea de este algoritmo es:

Elegir un elemento arbitrariamente. Este se denomina pivote.Pasar los elementos mas grandes que el pivote que estn a su izquierda, a su derecha.Pasar los elementos mas chicos que el pivote que estn a su derecha, a su izquierda.Dividir el arreglo en 2. Una parte del primer elemento hasta el pivote, y la otra el resto.Repetir los pasos anteriores con cada mitad.

Por ejemplo, con la siguiente lista:

18 11 27 14 9 4 16

Arbitrariamente el pivote ser el elemento del centro, es decir:

18 11 27 14 9 4 16

Busquemos el primer elemento mas grande a la izquierda del pivote, en este caso 18. Luego el ultimo mas chico a la derecha del pivote, eneste caso 4. Intercambindolos tenemos:

4 11 27 14 9 18 16

Captulo 7.


Busquemos el segundo elemento mas grande a la izquierda del pivote, en este caso 27. Luego el penltimo mas chico a la derecha del pivote,en este caso 9. Intercambindolos tenemos:

4 11 9 14 27 18 16

Ninguna de las sublistas esta ordenada, pero al ser mas corta la ordenacin ser mas rpida. Repitiendo el procedimiento con la primerasublista tenemos:

4 11 9 14

Eligiendo el pivote como 9:

4 11 9 14

Buscando el primer elemento mas grande a 9 tenemos el 11, pero como no hay otro elemento mas pequeo intercambiamos el pivote con el11. Tenemos:

4 9 11 14

Esta sublista ya esta ordenada.

Continuando con la segunda sublista tenemos:

27 18 16

Captulo 7.


Intercambiando el 27 con el 16 tenemos:

16 18 27

Esta sublista ya esta ordenada. Juntndolas tenemos:

4 9 11 14 16 18 27

El algoritmo correspondiente es:

void QuickSort(tipo * x, int n, int primero, int ultimo, int (* compara)(tipo, tipo)))

{

int grande=primero,chico=ultimo;

tipo pivote;

copia(&pivote, x[(primero+ultimo)/2]);

do {

while ((* compara)(x[grande],pivote)==-1)

grande++;

while ((* compara)(x[chico],pivote)==1)

chico--;

if (grande

Captulo 7.


if (primero < chico)

QuickSort(x, n, primero, chico, compara);

if (grande < ultimo )

QuickSort(x, n, grande, ultimo, compara);

}

Las funciones copia e intercambia son las mismas que en los mtodos anteriores.

El mtodo de QuickSort se programa mas fcilmente en forma recursiva, puesto que debe de repetirse cada vez con un vector cada vez maschico.

El ciclo do while realiza los intercambios entre los elementos mas grandes y mas chicos que el pivote. El pivote arbitrariamente se toma comoel elemento del centro.

El primer if verifica que todava se tenga un arreglo del lado izquierdo, si es as se llama a QuickSort recursivamente para que repita elprocedimiento.

El segundo if es anlogo pero checa el arreglo del lado derecho.

El tiempo medio de este algoritmo es:

Este tiempo es mejor que en los dems algoritmos. Por eso este algoritmo es mejor. Sin embargo en el peor caso el orden es:

Por lo regular esto no es un problema, ya que en la practica lo que ocurre con mayor frecuencia es el caso promedio.

1. ndice

7. Mtodos de bsqueda y ordenamiento. 7-17.1 Orden del mtodo 7-17.2 Mtodos de bsqueda 7-37.2.1 Bsquedasecuencial 7-47.2.2 Bsqueda binaria 7-57.3 Algoritmos de ordenamiento 7-77.3.1 Ordenamiento por insercin 7-77.3.2 Ordenamiento por burbuja o intercambio 7-87.3.3 Ordenacin rpida 7-97.4 Autoevaluacin 7-137.5 ndice7-16

sai.uam.mxCaptulo 7.

capítulo 7 busqueda y ordenamiento

Documents