Ordenacion por mezcla

Enviado por Programa Chuletas y clasificado en Otras materias

Escrito el en español con un tamaño de 11,04 KB

ORDENACION POR MEZCLA
La ordenacion por mezcla (MergeSort) utiliza un acercamiento al problema de ordenación muy diferente al utilizado por la ordenación por inserción. El ordenamiento por mezcla utiliza la técnica de Divide y Vencerás. La técnica de Divide y Vencerás utiliza basicamente tres pasos:
1. Divide: Dividir el problema en un cierto número de subproblemas.
2. Vence: Soluciona los problmeas de manera recursiva. Si el tamaño de los subproblemas es suficientemente pequeño, simplemente resuelvelos de la manera mas obvia.
3. Combina: Combina el resultado de los subproblemas para obtener la solución al problema original.
La ordenación por mezcla se apega estrictamente a la técnica. La idea del algoritmo es la siguiente:
1. Divide: Divide la secuencia de n elementos en dos subsecuencias de n/2 elementos.
2. Vence: Ordena ambas subsecuencias de manera recursiva.
3. Combina: Mezcla las dos subsecuencias ordenadas para obtener la solución del problema.
Para la solución recursiva cada subsecuencia a su vez se divide en dos sub-subsecuencias, y así hasta obtener una subsecuencia de tamaño 1, en este momento se detienen la recursión, ya que una subsecuencia de tamaño uno, siempre está ordenada.
La clave del ordenamiento por mezcla es precisamente la rutina que mezcla las dos subsecuencias ordenadas en una subsecuencia ordenada en el paso de
Combinación. En este ejemplo usaremos para esa función un procedimiento llamado Mezcla(A,p,q,r) donde A es un arreglo y p, q y r son índices del arreglo tales que p <= q < r. El procedimiento asume que los subarreglos A[p..q] y A[q + 1..r]están ordenados. El procedimiento mezcla estos dos subarreglos para formar un único arreglo ordenado en A[p..r].
Para explicar como funciona el procedimiento
Mezcla volvamos al ejemplo de las barajas. Supongamos ahora que se tienen dos montones de barajas, ordenados con las barajas hacia arriba, y deseamos mezclarlos en un único montón ordenado con las barajas hacia abajo. Al inicio ambos montones tienen a su carta más chica hasta arriba, el paso básico de nuestro algoritmo es comparar las barajas en la parte superior de cada montón, retirar la que sea más chica y ponerlas en nuestro montón de salida. Al quitar una baraja de uno de los montones, queda expuesta la siguiente baraja, por lo que podemos seguir, si alguno de los montones se llegara a terminar, entonces tomamos el montón que quedo y lo ponemos todo en nuestro montón de salida y listo, terminamos!
A continuación implementamos el procedimiento
Mezcla. Aunque este procedimiento no se analizará tan minuciosamente como el del ordenamiento por inserción, debe poder verse que su complejidad es de O(n) donde n=r - p + 1, es decir el número total de elementos a mezclar. Esto se debe a que cada elemento de cada uno de los dos submontones, se movio al montón de resultado únicamente una vez, por lo que si hay n elementos, el procedimiento tardará un tiempo proporcional a n.Mezcla(A,p,q,r) 1 n1:=q - p + 1 2 n2:=r - q 3 Crea arreglo L[1..n1 + 1] 4 Crea arreglo R[1..n2 + 1] 5 desde i:=1 hasta n1 haz 6 L[i]:=A[p + i - 1] 7 desde j:=1 hasta n2 haz 8 R[j]:=A[q + j] 9 L[n1 + 1]:=infinito 10 R[n2 + 1]:=infinitoMezcla(A,p,q,r) 1 n1:=q - p + 1 2 n2:=r - q 3 Crea arreglo L[1..n1 + 1] 4 Crea arreglo R[1..n2 + 1] 5 desde i:=1 hasta n1 haz 6 L[i]:=A[p + i - 1] 7 desde j:=1 hasta n2 haz 8 R[j]:=A[q + j] 9 L[n1 + 1]:=infinito 10 R[n2 + 1]:=infinito 11 i:=1 12 j:=1 13 desde k:=p hasta r haz inicio 14 Si L[i] <= R[j] entonces inicio 15 A[k]:=L[i] 16 i:=i + 1 17 Si-No entonces inicio 18 A[k]:=R[j] 19 j:=j + 1 20 fin-Si-entonces 21 fin-desde
En resumen, el procedimiento Mezcla funciona como sigue:
· Las líneas 1 y 2 calculan el largo del primer y segundo sub-arreglos.
· Las líneas 3 y 4 apartan memoria suficiente para los dos sub-arreglos.
· Los ciclos desde de las líneas 5, 6, 7 y 8 copian ambos sub-arreglos a los arreglos
L y R.
· En las líneas 9 y 10 se inicializa el último término de
L y R a infinito, esto es muy importante, ya que aqui el infinito nos sirve para saber cuando ya se terminó uno de los sub-arreglos. Aunque en cuestión práctica no existe tal cosa como "infinito" en las computadoras, se suele usar algún valor que previamente hayamos establecido como nuestro "infinito".
· El ciclo
desde que inicia en la línea 13 va desde p hasta r, es decir se ejecuta un número de veces igual a la suma de los elementos de ambos sub-arreglos. El funcionamiento de este ciclo es la idea básica del algoritmo. Compara el primer elemento no mezclado de cada sub-arreglo y retira el menor, avanzando hacia el siguiente elemento del sub-arreglo de donde se retiro el elemento.
Con el procedimiento
Mezcla podemos implementar nuestra ordenación por mezcla. El código del algoritmo queda de la siguiente forma
Ordena-Mezcla(A,p,r) 1 Si p < r entonces inicio 2 q:=(p + r) div 2 3 Ordena-Mezcla(A,p,q) // ORDENA LA MITAD IZQUIERDA 4 Ordena-Mezcla(A,q+1,r) // ORDENA LA MITAD DERECHA 5 Mezcla(A,p,q,r) 6 fin-Si-entonces
os recursivos no siempre resulta algo muy sencillo, sin embargo para el caso de la ordenación por mezcla se pueden seguir ciertos pasos que llevan a su análisis.
Como vimos anteriormente, la técnica de
divide y vencerás se basa en tres pasos básicos. Como con la ordenación por inserción sea T(n) el tiempo total que tarda el algoritmo en ordenar n elementos. Cuando n es suficientemente chico, digamos n <= c, entonces resolvemos el problema de la manera obvia, para este caso nuestro programa tarda un tiempo constante, por lo que podemos decir que tiene una complejidad de O(1). En general, supongamos que la division de nuestro problema nos entrega a subproblemas, cada uno de tamaño 1/b (para el caso de la ordenación por mezcla, tanto a como b son iguales a 2). Si tomamos que D(n) es el tiempo que tardamos en dividir el problema en subproblemas, y C(n), el tiempo que tardamos en combinar los subproblemas en una solución, entonces tenemos que

Hay un "teorema maestro" que sirve para resolver recurrencias de esta forma, sin embargo para varios casos, como el de la ordenación por mezcla, se puede ver de manera intuitiva cual va a ser el resultado. Revisemos paso a paso cada una de las partes.
·
Dividir: Para dividir, basta con cálcular cual es la mitad del arreglo, esto, se puede hacer sin ningún problema en tiempo constante, por lo que tenemos que para la ordenación por mezcla D(n) = O(1)
·
Vencer: Como dividimos el problema a la mitad y lo resolvemos recursivamente, entonces estamos resolviendo dos problemas de tamaño n/2 lo que nos da un tiempo T(n) = 2T(n/2)
·
Combinar: Vimos anteriormente que nuestro Mezcla era de orden lineal, por lo que tenemos que C(n)=O(n)
Para sustituir, sumamos
D(n) + C(n) = O(n) + O(1) = O(n), recordemos que para el análisis de complejidad únicamente nos importa el término que crezca más rápido. Por lo que sustituyendo en la recurrencia tenemos que:

donde
c representa una constante igual al tiempo que se requiera para resolver un problema de tamaño 1.
Sabemos que
n sólo puede ser dividido a la mitad lg n veces, por lo que la profundidad de nuestra recursión será de lgn, también del funcionamiento del algoritmo podemos ver que cada vez que dividamos a la mitad, vamos a tener que mezclar los n elementos, y sabemos que mezclar n elementos nos toma un tiempo proporcional a n, por lo que resolver la recursión debe tomar un tiempo proporcional a n lg n, que de hecho es la complejidad del algortimo. La ordenación por mezcla tiene una complejidad de O(n lg n).
Podemos comprobarlo, sustituyendo valores en la ecuación de recurrencia.
valor de n función de recurrencia tiempo total valor de n función de recurrencia tiempo total
1 c c 1 c c
2 2T(1) + 2c 2c + 2c = 4c = c(2 lg(2) + 2) 2 2T(1) + 2c 2c + 2c = 4c = c(2 lg(2) + 2)
4 2T(2) + 4c 8c + 4c =12c = c(4 lg(4) + 4) 4 2T(2) + 4c 8c + 4c =12c = c(4 lg(4) + 4)
8 2T(4) + 8c 24c+8c=32c=c(8 lg(8) + 8) 8 2T(4) + 8c 24c+8c=32c=c(8 lg(8) + 8)
. . . . . .
n 2T(n/2) + nc c(n lg(n) + n) n 2T(n/2) + nc c(n lg(n) + n)
De la tabla anterior vemos que el tiempo real de corrida del ordenamiento por mezcla es proporcional a n lg n + n, de nuevo, como en el análisis de complejidad únicamente nos importa el término que crezca más rápido y en ésta función ese término es n lg n, por lo tanto la complejidad del sistema es O(n lg n).

Entradas relacionadas: