Ordenar por fusión en Python

Merge Sort es uno de los algoritmos de clasificación más famosos debido a su uso eficiente y de propósito general. Es un ejemplo clásico de un algoritmo divide y vencerás. Lo implementaremos en Python en múltiples tipos de datos.

Introducción

Merge Sort es uno de los algoritmos de clasificación más famosos. Si estás estudiando Ciencias de la Computación, Merge Sort, junto con Ordenación rápida es probablemente el primer algoritmo de clasificación eficiente y de propósito general del que hayas oído hablar. También es un ejemplo clásico de una categoría de algoritmos divide y vencerás.

Clasificación por combinación

La forma en que funciona Merge Sort es:

Una matriz inicial se divide en dos partes aproximadamente iguales. Si la matriz tiene un número impar de elementos, una de esas "mitades" es un elemento más grande que la otra.

Los subarreglos se dividen una y otra vez en mitades hasta que terminas con arreglos que tienen solo un elemento cada uno.

Luego combina los pares de arreglos de un elemento en arreglos de dos elementos, clasificándolos en el proceso. Luego, estos pares ordenados se fusionan en matrices de cuatro elementos, y así sucesivamente hasta que termina con la matriz inicial ordenada.

Aquí hay una visualización de Merge Sort:

merge ordenar visualización

Como puede ver, el hecho de que la matriz no se pueda dividir en mitades iguales no es un problema, el 3 simplemente "espera" hasta que comience la clasificación.

Hay dos formas principales en las que podemos implementar el algoritmo Merge Sort, una es usando un enfoque de arriba hacia abajo como en el ejemplo anterior, que es la forma en que Merge Sort se presenta con mayor frecuencia.

El otro enfoque, es decir, de ​​abajo hacia arriba, funciona en la dirección opuesta, sin recursividad (funciona de forma iterativa): si nuestra matriz tiene N elementos, la dividimos en N subarreglos de un elemento y clasificamos pares de elementos adyacentes. arreglos de elementos, luego ordenar los pares adyacentes de arreglos de dos elementos y así sucesivamente.

Nota: El enfoque ascendente ofrece una optimización interesante de la que hablaremos luego. Implementaremos el enfoque de arriba hacia abajo ya que es más simple e intuitivo junto con el hecho de que no hay una diferencia real entre la complejidad del tiempo entre ellos sin optimizaciones específicas.

La parte principal de estos dos enfoques es cómo combinamos (fusionamos) las dos matrices más pequeñas en una matriz más grande. Esto se hace de manera bastante intuitiva, digamos que examinamos el último paso en nuestro ejemplo anterior. Tenemos las matrices:

-A: 2 4 7 8

-B: 1 3 11

  • ordenado: vacío

Lo primero que hacemos es mirar el primer elemento de ambas matrices. Encontramos el que es más pequeño, en nuestro caso que es 1, por lo que es el primer elemento de nuestra matriz ordenada, y avanzamos en la matriz B:

-A: 2 4 7 8

-B: 1 3 11

  • ordenado: 1

Luego miramos el siguiente par de elementos 2 y 3; 2 es más pequeño, así que lo ponemos en nuestra matriz ordenada y avanzamos en la matriz A. Por supuesto, no avanzamos en la matriz B y mantenemos nuestro puntero en 3 para futuras comparaciones:

-A: 2 4 7 8

-B: 1 3 11

  • ordenados: 1 2

Usando la misma lógica, nos movemos por el resto y terminamos con una matriz de {1, 2, 3, 4, 7, 8, 11}.

Los dos casos especiales que pueden ocurrir son:

  • Ambos subarreglos tienen el mismo elemento. Podemos avanzar en cualquiera de los dos y agregar el elemento a la matriz ordenada. Técnicamente, podemos avanzar en ambas matrices y agregar ambos elementos a la matriz ordenada, pero esto requeriría un comportamiento especial cuando encontramos los mismos elementos en ambas matrices.
  • Nos “quedamos” sin elementos en un subarreglo. Por ejemplo, tenemos una matriz con {1, 2, 3} y una matriz con {9, 10, 11}. Claramente, revisaremos todos los elementos de la primera matriz sin avanzar ni una sola vez en la segunda. Cada vez que nos quedamos sin elementos en un subarreglo simplemente agregamos los elementos del segundo uno tras otro.

Tenga en cuenta que podemos ordenar como queramos: este ejemplo ordena los números enteros en orden ascendente, pero podemos ordenar fácilmente en orden descendente u ordenar objetos personalizados.

Implementación

Implementaremos Merge Sort en dos tipos de colecciones: en matrices de enteros (generalmente se usan para introducir la clasificación) y en objetos personalizados (un escenario más práctico y realista).

Implementaremos el algoritmo Merge Sort utilizando el enfoque de arriba hacia abajo. El algoritmo no se ve muy "bonito" y puede ser confuso, así que revisaremos cada paso en detalle.

Clasificación de matrices {#clasificación de matrices}

Comencemos con la parte fácil. La idea base del algoritmo es dividir (sub)arreglos en mitades y ordenarlos recursivamente. Queremos seguir haciendo esto tanto como sea posible, es decir, hasta que terminemos con subarreglos que tengan un solo elemento:

1
2
3
4
5
6
7
8
def merge_sort(array, left_index, right_index):
    if left_index >= right_index:
        return

    middle = (left_index + right_index)//2
    merge_sort(array, left_index, middle)
    merge_sort(array, middle + 1, right_index)
    merge(array, left_index, right_index, middle)

Al llamar al método merge en último lugar, nos aseguramos de que todas las divisiones sucedan antes de comenzar la clasificación. Usamos el operador // para ser explícitos sobre el hecho de que queremos valores enteros para nuestros índices.

El siguiente paso es la parte de fusión real a través de algunos pasos y escenarios:

  • Crear copias de nuestras matrices. El primer arreglo es el subarreglo de [left_index,..,middle] y el segundo de [middle+1,...,right_index]
  • Revisamos ambas copias (haciendo un seguimiento de los punteros en ambas matrices), elegimos el más pequeño de los dos elementos que estamos viendo actualmente y los agregamos a nuestra matriz ordenada. Avanzamos en cualquier matriz de la que hayamos elegido el elemento y avanzamos en la matriz ordenada independientemente.
  • Si nos quedamos sin elementos en una de nuestras copias, simplemente agregue los elementos restantes en la otra copia a la matriz ordenada.

Con nuestros requisitos establecidos, avancemos y definamos una función merge():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def merge(array, left_index, right_index, middle):
    # Make copies of both arrays we're trying to merge

    # The second parameter is non-inclusive, so we have to increase by 1
    left_copy = array[left_index:middle + 1]
    right_copy = array[middle+1:right_index+1]

    # Initial values for variables that we use to keep
    # track of where we are in each array
    left_copy_index = 0
    right_copy_index = 0
    sorted_index = left_index

    # Go through both copies until we run out of elements in one
    while left_copy_index < len(left_copy) and right_copy_index < len(right_copy):

        # If our left_copy has the smaller element, put it in the sorted
        # part and then move forward in left_copy (by increasing the pointer)
        if left_copy[left_copy_index] <= right_copy[right_copy_index]:
            array[sorted_index] = left_copy[left_copy_index]
            left_copy_index = left_copy_index + 1
        # Opposite from above
        else:
            array[sorted_index] = right_copy[right_copy_index]
            right_copy_index = right_copy_index + 1

        # Regardless of where we got our element from
        # move forward in the sorted part
        sorted_index = sorted_index + 1

    # We ran out of elements either in left_copy or right_copy
    # so we will go through the remaining elements and add them
    while left_copy_index < len(left_copy):
        array[sorted_index] = left_copy[left_copy_index]
        left_copy_index = left_copy_index + 1
        sorted_index = sorted_index + 1

    while right_copy_index < len(right_copy):
        array[sorted_index] = right_copy[right_copy_index]
        right_copy_index = right_copy_index + 1
        sorted_index = sorted_index + 1

Ahora probemos nuestro programa:

1
2
3
array = [33, 42, 9, 37, 8, 47, 5, 29, 49, 31, 4, 48, 16, 22, 26]
merge_sort(array, 0, len(array) -1)
print(array)

Y la salida es:

1
[4, 5, 8, 9, 16, 22, 26, 29, 31, 33, 37, 42, 47, 48, 49]

Clasificación de objetos personalizados

Ahora que tenemos el algoritmo básico, podemos echar un vistazo a cómo ordenar las clases personalizadas. Podemos anular __eq__, __le__, __ge__ y otros operadores según sea necesario para esto.

Esto nos permite usar el mismo algoritmo que el anterior, pero nos limita a una sola forma de ordenar nuestros objetos personalizados, que en la mayoría de los casos no es lo que queremos. Una mejor idea es hacer que el algoritmo sea más versátil y, en su lugar, pasarle una función de comparación.

Primero implementaremos una clase personalizada, Car y le agregaremos algunos campos:

1
2
3
4
5
6
7
8
class Car:
    def __init__(self, make, model, year):
        self.make = make
        self.model = model
        self.year = year

    def __str__(self):
        return str.format("Make: {}, Model: {}, Year: {}", self.make, self.model, self.year)

Luego, haremos algunos cambios en nuestros métodos Merge Sort. La forma más fácil de lograr lo que queremos es usando funciones lambda. Puede ver que solo agregamos un parámetro adicional y cambiamos las llamadas al método en consecuencia, y solo otra línea de código para hacer que este algoritmo sea mucho más versátil:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def merge(array, left_index, right_index, middle, comparison_function):
    left_copy = array[left_index:middle + 1]
    right_copy = array[middle+1:right_index+1]

    left_copy_index = 0
    right_copy_index = 0
    sorted_index = left_index

    while left_copy_index < len(left_copy) and right_copy_index < len(right_copy):

        # We use the comparison_function instead of a simple comparison operator
        if comparison_function(left_copy[left_copy_index], right_copy[right_copy_index]):
            array[sorted_index] = left_copy[left_copy_index]
            left_copy_index = left_copy_index + 1
        else:
            array[sorted_index] = right_copy[right_copy_index]
            right_copy_index = right_copy_index + 1

        sorted_index = sorted_index + 1

    while left_copy_index < len(left_copy):
        array[sorted_index] = left_copy[left_copy_index]
        left_copy_index = left_copy_index + 1
        sorted_index = sorted_index + 1

    while right_copy_index < len(right_copy):
        array[sorted_index] = right_copy[right_copy_index]
        right_copy_index = right_copy_index + 1
        sorted_index = sorted_index + 1


def merge_sort(array, left_index, right_index, comparison_function):
    if left_index >= right_index:
        return

    middle = (left_index + right_index)//2
    merge_sort(array, left_index, middle, comparison_function)
    merge_sort(array, middle + 1, right_index, comparison_function)
    merge(array, left_index, right_index, middle, comparison_function)

Probemos o modifiquemos el algoritmo en algunas instancias de Car:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
car1 = Car("Alfa Romeo", "33 SportWagon", 1988)
car2 = Car("Chevrolet", "Cruze Hatchback", 2011)
car3 = Car("Corvette", "C6 Couple", 2004)
car4 = Car("Cadillac", "Seville Sedan", 1995)

array = [car1, car2, car3, car4]

merge_sort(array, 0, len(array) -1, lambda carA, carB: carA.year < carB.year)

print("Cars sorted by year:")
for car in array:
    print(car)

print()
merge_sort(array, 0, len(array) -1, lambda carA, carB: carA.make < carB.make)
print("Cars sorted by make:")
for car in array:
    print(car)

Obtenemos la salida:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Cars sorted by year:
Make: Alfa Romeo, Model: 33 SportWagon, Year: 1988
Make: Cadillac, Model: Seville Sedan, Year: 1995
Make: Corvette, Model: C6 Couple, Year: 2004
Make: Chevrolet, Model: Cruze Hatchback, Year: 2011

Cars sorted by make:
Make: Alfa Romeo, Model: 33 SportWagon, Year: 1988
Make: Cadillac, Model: Seville Sedan, Year: 1995
Make: Chevrolet, Model: Cruze Hatchback, Year: 2011
Make: Corvette, Model: C6 Couple, Year: 2004

Optimización

Vamos a elaborar la diferencia entre arriba-abajo y abajo-arriba Merge Sort ahora. Bottom-up funciona como la segunda mitad del enfoque top-down donde, en lugar de llamar recursivamente a la ordenación en subarreglos divididos por la mitad, ordenamos iterativamente los subarreglos adyacentes.

Una cosa que podemos hacer para mejorar este algoritmo es considerar fragmentos ordenados en lugar de elementos individuales antes de dividir la matriz.

Lo que esto significa es que, dada una matriz como {4, 8, 7, 2, 11, 1, 3}, en lugar de dividirla en {4}, {8}, {7}, {2 }, {11}, {1} ,{3} - se divide en subarreglos que ya pueden estar ordenados: *{4,8}, {7}, {2,11}, {1,3} *, y luego ordenarlos.

Con datos de la vida real, a menudo tenemos muchos de estos subarreglos ya ordenados que pueden acortar notablemente el tiempo de ejecución de Merge Sort.

Otra cosa a considerar con Merge Sort, particularmente la versión de arriba hacia abajo es el subproceso múltiple. Merge Sort es conveniente para esto, ya que cada mitad se puede ordenar independientemente de su par. Lo único de lo que debemos asegurarnos es de haber terminado de clasificar cada mitad antes de fusionarlas.

Sin embargo, Merge Sort es relativamente ineficiente (tanto en tiempo como en espacio) cuando se trata de matrices más pequeñas, y a menudo se optimiza deteniéndose cuando alcanzamos una matriz de \ ~ 7 elementos, en lugar de bajar a matrices con un elemento y llamando Tipo de inserción para ordenarlos en su lugar, antes de fusionarlos en una matriz más grande.

Esto se debe a que la ordenación por inserción funciona muy bien con arreglos pequeños y/o casi ordenados.

Conclusión

Merge Sort es un algoritmo de clasificación eficiente y de propósito general. Su principal ventaja es el tiempo de ejecución confiable del algoritmo y su eficiencia al clasificar matrices grandes. A diferencia de Quick Sort, no depende de ninguna decisión desafortunada que conduzca a malos tiempos de ejecución.

Uno de los principales inconvenientes es la memoria adicional que utiliza Merge Sort para almacenar las copias temporales de las matrices antes de fusionarlas. Sin embargo, Merge Sort es un ejemplo excelente e intuitivo para presentar a los futuros ingenieros de software el enfoque de dividir y vencer para crear algoritmos.

Hemos implementado Merge Sort tanto en matrices de enteros simples como en objetos personalizados a través de una función lambda utilizada para la comparación. Al final, se discutieron brevemente las posibles optimizaciones para ambos enfoques. oques.