Metodo de Ordenacion MergeSort

 

Fecha: 13/Jul/2005 (6/07/2005)
Autor: Jose Maria Quintanilla Rivera josemaria@ugb.edu.sv

 


Hola Amigos me parece interesante mostrar como se realiza la ordenación de un array a partir del método Mergesort utilizando el lenguaje C#. Por favor no se olviden de calificar este curso, su opinión cuenta, buena o mala será tomada en cuenta. Este método de ordenación utiliza recursividad por lo que se hace difícil realizarlo, ya que la recursividad consiste en un método que se invoca a si mismo. Este algoritmo está basado en la técnica de diseño de algoritmos Divide y Vencerás. El algoritmo de ordenación por mezcla, o Mergesort utiliza esta técnica para realizar la ordenación de una secuencia S de n elementos de la siguiente forma: 1. Si la secuencia tiene al menos dos elementos se divide en dos secuencias S1 y S2, S1 conteniendo los primeros én/2ù, y S2 con los restantes. 2. Recursivamente ordenar las secuencias S1 y S2. 3. Colocar los elementos de S mezclando los elementos de S1 y S2 que están ordenados de forma que en S queden ordenados.
La mezcla se realiza teniendo una referencia al principio de cada una de las secuencias a mezclar. Se inserta en la secuencia resultante el menor de los elementos referenciados y se avanza esa referencia una posición, mientras que en alguna cadena queden elementos. La mezcla de dos secuencias de longitudes n1 y n2 es O(n) donde n = n1 + n2, o sea, la longitud de la secuencia resultante.

A continuación veamos como queda el codigo en C#:

using System;

namespace mergesort
{
	class Class1
	{
		/// 
		/// ordenacion por mergesort o mezcla
		/// 
		[STAThread]
		public static void mergeSort(int [ ] x,int [ ] xTemp, int izq, int der)
		{
			if(izq < der)
			{
				int medio = (izq + der)/2;
				mergeSort(x,xTemp,izq,medio);
				mergeSort(x,xTemp,medio+1,der);
				mezclar(x,xTemp,izq,medio+1,der);
			}
		}

public static void mezclar (int [ ] x,int [ ] xAux,int posIzq, int posDer,int posFin)
		{
			int finIzq = posDer - 1;
			int posAux = posIzq;
			int numElementos = posFin - posIzq +1;
			// Bucle principal
			while(posIzq <= finIzq && posDer <= posFin)
				if( x[posIzq] < x[posDer] )
					xAux[posAux++] = x[posIzq++];
				else
			xAux[posAux++] = x[posDer++];
			// Copiar el resto de la primera mitad
			while (posIzq <= finIzq)
			xAux[posAux++] = x[posIzq++];
			// Copiar el resto de la segunda mitad
			while (posDer <= posFin)
			xAux[posAux++] = x[posDer++];
			// Copiar el vector temporal en el original
			for(int i = 0; i < numElementos; i++, posFin--)
			x[posFin] = xAux[posFin];
		}
		static void Main(string[] args)
		{
			int []arreglo= new int [7];
			int []temporal=new int [7];
			for(int c=0;c<7;c++)
				arreglo[c]=0;
			for(int c=0;c<7;c++)
				temporal[c]=0;
			Console.WriteLine ("Introduzca valores al arreglo");
			for(int c=0;c<7;c++)
				arreglo[c]=int.Parse (Console.ReadLine ());
			Console.WriteLine ("Ordenando el arreglo...");
			mergeSort(arreglo,temporal, 0, 6);
			Console.WriteLine ("Arreglo ordenado...");
			for(int c=0;c<7;c++)
			Console.WriteLine (arreglo[c]);

		}
	}
}

 

Recuerda evaluar este Articulo, tu opinion Cuenta.



 


Espacios de nombres usado en el código de este artículo:

System


Fichero con el código de ejemplo: josemaria_ordenacion_CLASS1.ZIP - 1 KB


ir al índice