CLASIFICACION POR MEZCLAS

Clasificacion por mezclas

Llohanna Alonso

David Blanco

Martil Gaitan

El método de clasificación por mezcla resulta apropiado cuando la colección de elementos a clasificar está representada mediante una lista enlazada, y no lo es tanto para una lista con representación contigua por la cantidad de espacio que necesitaría. El método usa la técnica divide y vencerás de la siguiente forma.Si la lista está constituida por un único elemento o es vacía, entonces está ya clasificada. En caso contrario, se divide la lista en dos sublistas de igual tamaño y se clasifican ambas (la recursividad resulta entonces idónea para ordenar ambas sublistas). Finalmente, las dos sublistas clasificadas se mezclan en una única, que será la lista original clasificada. El tiempo de ejecución requerido por el método es O(nlogn) (tanto en el caso promedio como en el peor caso), y es debido a que es posible mezclar dos listas clasificadas para obtener una única lista también clasificada en un tiempo de ejecución O(n).Ya que la división de una lista en dos sublistas del mismo tamaño se puede hacer también en un tiempo de ejecución O(n), y el árbol de expansión de la recursividad es de profundidad logn al tratarse de un árbol binario balanceado, el tiempo de ejecución total del algoritmo es de O(nlogn) (el cálculo del tiempo de ejecución del algoritmo para los casos peor y promedio es equivalente al cálculo del tiempo de ejecución del algoritmo quicksort para el caso promedio).

clasificacion por mezclas

Clasificación por mezclas

Llohanna Alonso

David Blanco

Martil Gaitan

El método de clasificación por mezcla resulta apropiado cuando la colección de elementos a clasificar está representada mediante una lista enlazada, y no lo es tanto para una lista con representación contigua por la cantidad de espacio que necesitaría.

Tecnica

El método usa la técnica divide y vencerás de la siguiente forma.Si la lista está constituida por un único elemento o es vacía, entonces está ya clasificada. En caso contrario, se divide la lista en dos sublistas de igual tamaño y se clasifican ambas (la recursividad resulta entonces idónea para ordenar ambas sublistas). Finalmente, las dos sublistas clasificadas se mezclan en una única, que será la lista original clasificada.

Tiempo

El tiempo de ejecución requerido por el método es O(nlogn) (tanto en el caso promedio como en el peor caso), y es debido a que es posible mezclar dos listas clasificadas para obtener una única lista también clasificada en un tiempo de ejecución O(n).Ya que la división de una lista en dos sublistas del mismo tamaño se puede hacer también en un tiempo de ejecución O(n), y el árbol de expansión de la recursividad es de profundidad logn al tratarse de un árbol binario balanceado, el tiempo de ejecución total del algoritmo es de O(nlogn) (el cálculo del tiempo de ejecución del algoritmo para los casos peor y promedio es equivalente al cálculo del tiempo de ejecución del algoritmo quicksort para el caso promedio).

clasificacion por mezclas

Clasificacion por mezcla

David Blanco

Martil Gaitan

Llohanna Alonso

El método de clasificación por mezcla resulta apropiado cuando la colección de elementos a clasificar está representada mediante una lista enlazada, y no lo es tanto para una lista con representación contigua por la cantidad de espacio que necesitaría.

Tecnica

El método usa la técnica divide y vencerás de la siguiente forma.Si la lista está constituida por unúnico elemento o es vacía, entonces está ya clasificada. En caso contrario, se divide la lista en dos sublistas de igual tamaño y se clasifican ambas (la recursividad resulta entonces idónea para ordenar ambas sublistas). Finalmente, las dos sublistas clasificadas se mezclan en una única, que será la lista original clasificada.

Tiempo

El tiempo de ejecución requerido por el método es O(nlogn) (tanto en el caso promedio como en el peor caso), y es debido a que es posible mezclar dos listas clasificadas para obtener una única lista también clasificada en un tiempo de ejecución O(n).Ya que la división de una lista en dos sublistas del mismo tamaño se puede hacer también en un tiempo de ejecución O(n), y el árbol de expansión de la recursividad es de profundidad logn al tratarse de un árbol binario balanceado, el tiempo de ejecución total del algoritmo es de O(nlogn) (el cálculo del tiempo de ejecución del algoritmo para los casos peor y promedio es equivalente al cálculo del tiempo de ejecución del algoritmo quicksort para el caso promedio).

Búsqueda Binaria

por

Pedro Gonzalez y Vivian Martinez

La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:
Se toma el elemento central y se divide el array en dos: {1,2,3,4}−5-{6,7,8,9} Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4} Se vuelve a dividir el array en dos: {1}−2-{3,4} Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4} Se vuelve a dividir en dos: {}−3-{4} Como el elemento buscado coincide con el central, lo hemos encontrado.
Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array. La implementación sería:
int desde,hasta,medio,elemento,posicion; // desde y
// hasta indican los límites del array que se está mirando.
int array[N];
// Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta;) { if(desde==hasta) // si el array sólo tiene un elemento:
{
if(array[desde]==elemento) // si es la solución:
posicion=desde; // darle el valor.
else // si no es el valor:
posicion=−1; // no está en el array.
break; // Salir del bucle.
}
medio=(desde+hasta)/2; // Divide el array en dos.
if(array[medio]==elemento) // Si coincide con el central:
{
posicion=medio; // ese es la solución
break; // y sale del bucle.
}
else if(array[medio]>elemento) // si es menor:
hasta=medio-1; // elige el array izquierda.
else // y si es mayor:
desde=medio+1; // elige el array de la derecha.
}
En general, este método realiza log(2,N+1) comparaciones antes de encontrar el elemento, o antes de descubrir que no está. Este número es muy inferior que el necesario para la búsqueda lineal para casos grandes.
Este método también se puede implementar de forma recursiva, siendo la función recursiva la que divide al array en dos más pequeños .