El ordenamiento por mezcla (merge sort) utiliza una estrategia dividir y conquistar. El algoritmo inicialmente divide el arreglo en dos partes (sub-arreglos) y llama recursivamente la función de ordenamiento para ordenar cada parte por separado. Después las dos subarreglos son mezclados para obtener un arreglo totalment ordenado al final.
La siguiente función se encarga de hacer la mezcla de dos sub arreglos adyacentes que deben estar ordenados inicialmente. Los subarreglos se encuentran en las posiciones A[p:q + 1]
y A[q + 1:r + 1]
respectivamente. Al finalizar el subarreglo A[p:r + 1]
debe estar ordenado ascendentemente.
def merge(A, p, q, r):
# print 'merging (%d, %d, %d)'%(p, q, r)
L = A[p:q+1]+[float('inf')]
R = A[q+1:r+1]+[float('inf')]
i = 0
j = 0
for k in range(p, r + 1):
if L[i] <= R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
B = [1, 3, 5, 7, 2, 4, 8, 10, 11]
merge(B, 0, 3, 8)
print B
[1, 2, 3, 4, 5, 7, 8, 10, 11]
La siguiente función, merge_sort_main(A, p, r)
, implementa el algoritmo de ordenamiento por mezcla. Inicialmente divide el subarreglo A[p:r +1]
en dos subarreglos calculando q
. Llama recursivamente la función sobre los dos subarreglos y finalmente mezcla los resultados mediante un llamado a la función merge(A, p, q, r)
.
def merge_sort_main(A, p, r):
if p < r:
q = int((p + r) / 2.0)
merge_sort_main(A, p, q)
merge_sort_main(A, q + 1, r)
merge(A, p, q, r)
def merge_sort(A):
merge_sort_main(A, 0, len(A) - 1)
B = range(10, 0, -1)
merge_sort(B)
print B
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Para analizar el tiempo de ejecución del ordenamiento por mezcla definimos una función que recibe una función de ordenamiento y un arreglo y calcula el tiempo que toma la función para ordenar el arreglo. La función time.time()
calcula el tiempo actual en segundos. Esta función es usada para calcular el tiempo antes y después de invocar el función de ordenamiento. Este proceso se realiza 10 veces y se reporta el promedio. La función gc.collect()
invoca el recolector de basura en memoria de manera que una eventual recolección de basura no afecte el cálculo del tiempo.
import time
import gc
def calc_time(sort_function, array):
timesum = 0
gc.collect()
for i in range(10):
array_copy = list(array)
tic = time.time();
sort_function(array_copy)
toc = time.time();
timesum += toc - tic
return timesum/10
Función de ordenamiento por inserción para comparar con el ordenamiento por mezcla.
def insertion_sort(A):
j = 1
while j < len(A):
key = A[j]
i = j - 1
while (i >= 0) and (A[i] > key):
A[i + 1] = A[i]
i = i -1
A[i + 1] = key
j = j + 1
print calc_time(insertion_sort, range(1000,1,-1))
0.127943897247
La siguiente función calcula tiempos de ordenamiento para diferentes arreglos de diferente tamaño.
import random as rnd
def exper_analysis(sizes):
results_merge = []
results_insertion = []
for i in sizes:
list1 = range(i)
rnd.shuffle(list1)
results_merge.append(calc_time(merge_sort, list1))
results_insertion.append(calc_time(insertion_sort, list1))
return (results_merge, results_insertion)
import numpy as np
import pylab as pl
%matplotlib inline
pl.clf()
sizes = np.arange(10,700,10)
(y1,y2) = np.array(exper_analysis(sizes))
pl.plot(sizes, y1, 'k.', label = 'Merge sort')
pl.plot(sizes, y2, 'bx', label = 'Insertion sort')
pl.xlabel('Array size')
pl.ylabel('Seconds')
pl.legend(loc = 'upper left')
<matplotlib.legend.Legend at 0x10fe25990>
El ordenamiento por mezcla funciona más efecientemente que el ordenamiento por inserción para arreglos suficientemente grandes, para arreglos con tamaños por debajo de 80, funciona más eficientemente ordenamiento por inserción ¿Como podemos mejorar el ordenamiento por mezcla teniendo esto en cuenta?