Google+ Seguidores

miércoles, 15 de agosto de 2018

Ordenamiento por Mezcla ("Merge Sort") - Algoritmos de Ordenamiento

Introducción:

Hola amigos de Internet, bienvenidos a Mi Diario Python, el mejor blog para Aprender Python.

En este árticulo, nos dedicaremos a conocer el algoritmo de ordenamiento "Ordenamiento por Mezcla", más conocido como Merge Sort.

Veremos sus características, su pseudocódigo y al final realizaremos una implementación en el lenguaje de programación Python.

¿Que te parece? Comencemos.

Ordenamiento por Mezcla

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás.

La idea de los algoritmos de ordenación por mezcla es dividir la matriz por la mitad una y otra vez hasta que cada pieza tenga solo un elemento de longitud. Luego esos elementos se vuelven a juntar (mezclados) en orden de clasificación.

A continuación les mostrare una representación del algoritmo en acción:


Comenzamos dividiendo la matriz:

[31,4,88,2,4,2,42]
[31,4,88,1][4,2,42] Dividimos en 2 partes

[31,4][88,1][4,2][42] Dividimos en 4 partes

[31][4][88][1][4][2][42] Piezas individuales

Ahora tenemos que unirlos de nuevo en orden de mezcla:

Primero fusianamos elementos individuales en pares. Cada par se fusiona en orden de mezcla.

[4,31][1,88][2,4][42]

Luego fusionamos los pares en orden de mezcla:

[1,4,31,88][2,4,42]

Y luego fusionamos los dos últimos grupos.

[1,2,4,4,31,42,88]

Y listo, nuestra lista esta ordenada.

Sí, lo se, al principio puede ser que nos confundamos un poco.

Pseudocódigo del algoritmo:


El pseudocódigo del algoritmo es este (Gracias a nuestros infiltrados en Wikipedia):

function mergesort(m)
  var list left, right, result
  if length(m) ≤ 1
      return m
  else
      var middle = length(m) / 2
      for each x in m up to middle - 1
          add x to left
      for each x in m at and after middle
          add x to right
      left = mergesort(left)
      right = mergesort(right)
      if last(left) ≤ first(right) 
         append right to left
         return left
      result = merge(left, right)
      return result

function merge(left, right)
  var list result
  while length(left) > 0 and length(right) > 0
      if first(left) ≤ first(right)
          append first(left) to result
          left = rest(left)
      else
          append first(right) to result
          right = rest(right)
  if length(left) > 0 
      append rest(left) to result
  if length(right) > 0 
      append rest(right) to result
  return result

Como pueden observar, son dos funciones. La primera, merge_sort, ordena la lista, mientras que la segunda, merge, se encarga de intercalar los elementos de las listas left y right que merge recibe como parámetros.

Implementación del algoritmo:

No hay nada como un ejemplo para entender mejor como funciona algo. 

Realizaremos un implemntación del algoritmo y sus dos funciones, basándonos en el pseudocódigo mostrado anteriormente.

Puedes ver y dercargar todo el código ingresando al siguiente enlace: https://gist.github.com/LuisAlejandroSalcedo/1275c76efa33d6bbead0c8c5ae1f8f1e.

# Función merge_sort
def merge_sort(lista):
 
   """
   Lo primero que se ve en el psudocódigo es un if que
   comprueba la longitud de la lista. Si es menor que 2, 1 o 0, se devuelve la lista.
   ¿Por que? Ya esta ordenada. 
   """
   if len(lista) < 2:
      return lista
    
    # De lo contrario, se divide en 2
   else:
        middle = len(lista) // 2
        right = merge_sort(lista[:middle])
        left = merge_sort(lista[middle:])
        return merge(right, left)
    
# Función merge
def merge(lista1, lista2):
    """
    merge se encargara de intercalar los elementos de las dos
    divisiones.
    """
    i, j = 0, 0 # Variables de incremento
    result = [] # Lista de resultado
 
   # Intercalar ordenadamente
    while(i < len(lista1) and j < len(lista2)):
        if (lista1[i] < lista2[j]):
            result.append(lista1[i])
            i += 1
        else:
            result.append(lista2[j])
            j += 1
 
   # Agregamos los resultados a la lista
    result += lista1[i:]
    result += lista2[j:]
 
    # Retornamos el resultados
    return result

# Prueba del algoritmo

lista = [31,3,88,1,4,2,42]

merge_sort_result = merge_sort(lista)  
print(merge_sort_result)

[1, 2, 3, 4, 31, 42, 88]

Como pueden apreciar, el resultado es satisfactorio.

He utilizado la misma lista que use en el ejemplo del principio.

¿Que te parecio? ¿Alguna duda? No dudes en dejar tu comentario.

Mi nombre es Luis, y fue un placer compartir mis conocimientos con todos ustedes :D.

No hay comentarios :
Write comentarios

Tu comentario es importante y nos motiva a seguir escribiendo...

Powered by Blogger .