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.
Deja una respuesta
Gracias Luis me ayudo a entender mejor este algoritmo