Algoritmo de Ordenación MergeSort

Este método se basa en la técnica "divide y vencerás". Los pasos que aplica son los siguientes:
  1. Se divide el vector en dos mitades.
  2. Se ordena cada una de las dos mitades aplicando MergeSort.
  3. Se mezclan ambas mitades, obteniendo un vector ordenado.
La operación de división se aplica, recursivamente, a cada una de las dos mitades obtenidas en cada paso. Cuando la partición obtenida tenga un solo elemento se la considera ordenada. A continuación se mezclarán las particiones de un elemento, obteniendo particiones ordenadas de dos elementos. El proceso de mezcla continuará, obteniendose particiones ordenadas cada vez más grandes, hasta obtener todo el vector ordenado.
La operación de mezcla de dos vectores ordenados genera un nuevo vector que contiene los elementos de ambos y que conserva el orden. En este caso los dos vectores que se pretenden mezclar son realmente dos intervalos de posiciones del vector que estamos intentando ordenar. El primer subvector será el que comprende las posiciones IZQ a CEN del vector original, mientras que el segundo comprende las posiciones CEN+1 a DER.
Para realizar la mezcla, se comparan dos elementos de ambos subvectores, copiando en el destino el menor de ellos. A continuación se toma otro elemento del mismo origen del que se acaba de copiar el valor en el destino y prosigue la comparación. El proceso concluye cuando se hayan copiado, en el destino, todos los elementos de algún origen. En ese momento se copian, en el destino, todos los elementos del otro origen que aún no se hayan copiado.
Se utilizará un vector auxiliar, llamado TEMP, que permitirá almacenar, durante el proceso de mezcla, los valores que se están mezclando. Concluida la mezcla, se copian los elementos de este vector sobre el original, considerando sólo las posiciones del vector TEMP comprendidas entre IZQ y DER.
PSEUDOCÓDIGO
    MÓDULO ordenacion_por_mezcla

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe IZQ entera
           Recibe DER entera
       VARIABLES
           CEN entera
    INICIO
           Si ( IZQ < DER ) entonces
               CEN <- (IZQ+DER)\2      ** división entera
               ordenacion_por_mezcla(V, IZQ, CEN)
               ordenacion_por_mezcla(V, CEN+1, DER)
               mezclar(V, IZQ, CEN, DER)
           fin-si
    FIN

    MÓDULO mezclar

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe IZQ entera
           Recibe CEN entera
           Recibe DER entera
       VARIABLES
           TEMP() de tipo T
           I1, I2, I_TEMP entera
    INICIO
           I1 <- IZQ  
           I2 <- CEN+1
           I_TEMP <- IZQ
           Mientras( (I1 ≤ CEN)  y  (I2 ≤ DER) ) hacer
               Si ( V(I1) < V(I2) ) entonces
                   TEMP(I_TEMP) <- V(I1)
                   I1 <- I1 + 1
               sino
                   TEMP(I_TEMP) <- V(I2)
                   I2 <- I2 + 1
               fin-si
               I_TEMP <- I_TEMP + 1
           fin-mientras
           Mientras (I1 ≤ CEN) hacer
               TEMP(I_TEMP) <- V(I1)
               I1 <- I1 + 1
               I_TEMP <- I_TEMP + 1
           fin-mientras
           Mientras (I2 ≤ DER) hacer
               TEMP(I_TEMP) <- V(I2)
               I2 <- I2 + 1
               I_TEMP <- I_TEMP + 1
           fin-mientras
           Para I_TEMP desde IZQ hasta DER
               V(I_TEMP) <- TEMP(I_TEMP)
           fin-para
    FIN

CÓDIGO C
/*Ordena un vector (de menor a mayor) por el método de mergeSort
**Nota: Utiliza Divide y vencerás */
mergeSort(int *v, int izq, int der)
{
int cen;

	if(izq<der)
	{
	cen=(izq+der)/2;
	mergeSort(v,izq,cen);
	mergeSort(v,cen+1,der);
	mezclar(v,izq,cen,der);
	}
}



mezclar(int *v,int izq,int cen,int der)
{
int temp[der+1], i1, i2,itemp;

i1=izq;
i2=cen+1;
itemp=izq;

	while((i1<=cen) && (i2<=der))
	{
		if(v[i1]<v[i2])
		{
		temp[itemp]=v[i1];
		i1=i1+1;
		}
		else
		{
		temp[itemp]=v[i2];
		i2=i2+1;
		}
	itemp=itemp+1;
	}

	while(i1<=cen)
	{
	temp[itemp]=v[i1];
	i1=i1+1;
	itemp=itemp+1;
	}

	while(i2<=der)
	{
	temp[itemp]=v[i2];
	i2=i2+1;
	itemp=itemp+1;
	}

	for(itemp=izq;itemp<=der;itemp++)
	{
	v[itemp]=temp[itemp];
	}
}

Volver al índice

Volver a Búsqueda y Ordenación Interna



Comentarios

Publicar un comentario

Entradas populares de este blog

Algoritmo de ordenación por mezcla natural

El método de ordenación por mezcla natural, al igual que el de clasificación por mezcla directa, realiza sucesivas particiones y mezclas, pero intenta aprovechar el orden existente en los datos, considerando secuencias de longitud variable. En cada iteración, en primer lugar se separan los registros del fichero origen en otros dos ficheros, copiando en cada uno las secuencias de registros consecutivos que ya están ordenados entre sí en el origen. A continuación, se mezclan los dos ficheros auxiliares, obteniendo de cada dos tramos ordenados otro ordenado. El proceso de ordenación se repite hasta que se obtiene un solo tramo. PSEUDOCÓDIGO MÓDULO Clasificacion_mezcla_natural DATOS PARÁMETROS Recibe NOMBRE_F cadena ** fichero a ordenar Recibe NOMBRE_F1 cadena ** primer fichero auxiliar Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar VARIABLES L entera ** num. de subsecuencias ordenadas mez...
Leer más

Algoritmo de ordenación por mezcla directa

La ordenación por mezcla directa realiza sucesivas operaciones de partición y mezcla, que producen secuencias ordenadas de longitud cada vez mayor. La primera partición se hace en secuencias de longitud 1, y la fusión correspondiente produce sobre el archivo inicial secuencias ordenadas de longitud 2. En cada nueva partición y fusión se duplica la longitud de las secuencias ordenadas obtenidas. El proceso termina cuando la longitud de la secuencia ordenada es mayor o igual que la longitud del archivo a ordenar. PSEUDOCÓDIGO MÓDULO Ordenacion_mezcla_directa DATOS PARÁMETROS Recibe NOMBRE_F cadena ** fichero a ordenar Recibe NOMBRE_F1 cadena ** primer fichero auxiliar Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar VARIABLES NUM_ELEM entero ** num. de registros a ordenar TAM_SEC entero ** tamaño de la secuencia actual INICIO TAM_SEC ← 1 ...
Leer más

Algoritmo de Ordenación por Intercambio Directo (Burbuja)

Este método también se conoce como método de la burbuja. Tiene dos versiones basadas en la misma idea: recorrer sucesivamente el vector comparando los elementos consecutivos e intercambiándolos cuando estén descolocados. En una de las versiones el vector se recorre de izquierda a derecha, desplazando los valores mayores hacia su derecha, y en la otra se recorre de derecha a izquierda, desplazando los valores menores hacia su izquierda, ambos para la clasificación en orden ascendente. Cada pasada sobre el vector lleva un nuevo elemento a su posición definitiva, y en orden, en el extremo de la zona de comparación considerada (extremo derecho en el caso de recorrido de izquierda a derecha y en el extremo izquierdo en el caso de recorrido de derecha a izquierda), por lo que en la siguiente pasada se excluye de las comparaciones. El algoritmo consiste en aplicar los siguientes pasos, considerando inicialmente todas las posiciones del vector: Se comparan los valores de las posicione...
Leer más