Ordenación por mezcla en C#

Abr 2, 2011 Codigos C# 8 comentarios

Ya he publicado algunos algoritmos de ordenación como Ordenación por burbuja (Bubble Sort) y Ordenación Rápida (Quick Sort) implementados con C#. Esta vez estaremos hablando de Ordenación por Mezcla (Merge Sort), otro algoritmo recursivo bastante eficiente para ordenar un array, que tiene un orden de complejidad O(nlogn) al igual que Quick Sort. Fue desarrollado en 1945 por John Von Neumann según wikipedia.

Estrategia de Merge Sort

Merge Sort está basado en la técnica de diseño de algoritmos Divide y Vencerás, de la cual se habló aquí mismo hace un tiempo. Recordando un poco, esta técina consiste en dividir el problema a resolver en subproblemas del mismo tipo que a su vez se dividirán, mientras no sean suficientemente  pequeños o triviales.

merge Ordenación por mezcla en C#

Veamos una panorámica de la estrategia que sigue este algoritmo para ordenar una secuencia S de n elementos:

  • Si S tiene uno o ningún elemento, está ordenada
  • Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2
  • S1 contiene los primeros n/2 elementos y S2 los restantes
  • Ordenar S1 y S2, aplicando recursivamente este procedimiento
  • Mezclar S1 y S2 en S, de forma que ya S1 y S2 estén ordenados

Veamos ahora como sería la estrategia para mezclar las secuencias:

Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2). Mientras en alguna secuencia queden elementos, se inserta en la secuencia resultante (S) el menor de los elementos referenciados y se avanza esa referencia una posición.

Pseudocódigo

Como ven, la idea es bastante simple, pero programarla no tanto. Para no dar de golpe la solución, veamos primero un pseudocódigo del algoritmo:

function mergesort(array A[x..y])
begin
  if (x-y > 1)):
    array A1 := mergesort(A[x..(int( x+y / 2))])
    array A2 := mergesort(A[int(1+(x+y / 2))..y])
    return merge(A1, A2)
  else:
    return A
end

function merge(array A1[0..n1], array A2[0..n2])
begin
  integer p1 := 0
  integer p2 := 0
  array R[0..(n1 + n2 + 2)]//suponiendo que n1 y n2 son las posiciones
  //del array y no el length de este mismo, de otro modo seria (n1 + n2)
  while (p1 <= n1 or p2 <= n2):
    if (p1 <= n1 and A1[p1] <= A2[p2]):
      R[p1 + p2] := A1[p1]
      p1 := p1 + 1

    else
      if (p2 <= n2 and A1[p1] > A2[p2]):
        R[p1 + p2] := A2[p2]
        p2 := p2 + 1
  return R
end

El código

Básicamente, el pseudocódigo sigue la estrategia descrita anteriormente. Veamos el código en C# de una vez:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeSort
{
 class Program
 {
    static void Main(string[] args)
    {
       //Array desordenado inicial
       int[] nums = new int[] { 2, 7, 4, 7, 2, 9, 13, 4, 6, 8 };
       MergeSort(nums);

       //Imprimo el array ya ordenado
       for (int i = 0; i < nums.Length; i++)
          Console.Write(nums[i]+" ");
       Console.ReadLine();
    }

    //Método portal que llama al método recursivo inicial
    public static void MergeSort(int[] x)
    {
       MergeSort(x, 0, x.Length - 1);
    }

    static private void MergeSort(int[] x, int desde, int hasta)
    {
       //Condicion de parada
       if (desde == hasta)
          return;

       //Calculo la mitad del array
       int mitad = (desde + hasta) / 2;

       //Voy a ordenar recursivamente la primera mitad
       //y luego la segunda
       MergeSort(x, desde, mitad);
       MergeSort(x, mitad + 1, hasta);

       //Mezclo las dos mitades ordenadas
       int[] aux = Merge(x, desde, mitad, mitad + 1, hasta);
       Array.Copy(aux, 0, x, desde, aux.Length);
    }

    //Método que mezcla las dos mitades ordenadas
    static private int[] Merge(int[] x, int desde1, int hasta1, int desde2, int hasta2)
    {
       int a = desde1;
       int b = desde2;
       int[] result = new int[hasta1 - desde1 + hasta2 - desde2 + 2];

       for (int i = 0; i < result.Length; i++)
       {
          if (b != x.Length)
          {
             if (a > hasta1 && b <= hasta2)
             {
                result[i] = x[b];
                b++;
             }
             if (b > hasta2 && a <= hasta1)
             {
                result[i] = x[a];
                a++;
             }
             if (a <= hasta1 && b <= hasta2)
             {
                if (x[b] <= x[a])
                {
                   result[i] = x[b];
                   b++;
                }
                else
                {
                   result[i] = x[a];
                   a++;
                }
             }
          }
          else
          {
             if (a <= hasta1)
             {
                result[i] = x[a];
                a++;
             }
          }
       }
       return result;
    }
  }
}

Este código lo hice cuando estaba en 1er año, y ahora que lo veo (que ya estoy en 3ro), veo se que se pueden hacer unas cuantas mejoras, pero funciona perfectamente y está bastante comprensible, sobre todo para quien no está familiarizado con el algoritmo y la recursividad.

De todas formas dejo el zip para que puedan descargar el proyecto completo, lo único es que está en Visual Studio 2010. Si tienen alguna duda o aporte, en los comentarios.

Compartir:

Relacionados

algunos artículos que te pueden interesar

8 comentarios

Forma parte de nuestra discusión y síguela de cerca

Es verdad que se le pueden hacer algunas mejoras pero esta bastante bueno y facil de entender, gracias por compartilo en la web. un saludo desde Cuba.

Autor: michel | Fecha: Oct 6, 2011.

Para eso es este blog, para compartir… saludos desde La Habana

Autor: Tomy | Fecha: Oct 6, 2011.

podrias excribir el algoritmo que mezcla recursivamente?

Autor: borja | Fecha: Ene 17, 2012.

El algoritmo en C# es recursivo, fíjate en las llamadas:
MergeSort(x, desde, mitad);
MergeSort(x, mitad + 1, hasta);

Autor: Tomy | Fecha: Ene 19, 2012.

Gracias por tu aportación amigo, esta muy bueno tu codigo me gustaria aprender más sobre programar, sabes apenas me estoy iniciando en esto y me llama la atención mucho pero se me dificulta tambien a la vez

Autor: CESAR | Fecha: Mar 13, 2012.

@CESAR: Todo es cuestión de práctica y esfuerzo… nadie ha dicho que programar es sencillo, y menos programar bien. Yo llevo como 5 años programando y todavía estoy muy lejos de ser buen programador.

Autor: Tomy | Fecha: Mar 23, 2012.

Hola, me gustaría saber si es posible representar ese mismo algoritmo pero en pseudocodigo…? Gracias
SALUDOS DESDE COLOMBIA

Autor: Jair | Fecha: Oct 4, 2012.

Hola. el código lo he probado pero solo sale una parte del ordenamiento me gustaría que lo veas en que esta mal.

Autor: karen | Fecha: Jun 18, 2014.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.