Combinar ordenar en Python

C

Introducción

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

Combinar ordenar

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 el otro.

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 matrices de un elemento en matrices de dos elementos, clasificándolos en el proceso. Luego, estos pares ordenados se fusionan en matrices de cuatro elementos, y así sucesivamente hasta que termine con la matriz inicial ordenada.

Aquí hay una visualización de Merge Sort:

Como puede ver, el hecho de que la matriz no se pueda dividir en mitades iguales no es un problema, las 3 simplemente “esperan” 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 introduce 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 submatrices de un elemento y ordenamos pares de matrices adyacentes de un elemento, luego ordenamos pares adyacentes de matrices de dos elementos y así sucesivamente.

Nota: El enfoque ascendente proporciona una optimización interesante que discutiremos más adelante. 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 ambos 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:

  • UN: 2 4 7 8
  • SEGUNDO: 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 es 1, por lo que ese es el primer elemento de nuestra matriz ordenada, y avanzamos en la matriz B:

  • UN: 2 4 7 8
  • B: 1 3 11
  • ordenados: 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. Siempre que nos quedemos 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 números enteros (normalmente utilizados para introducir la ordenació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 repasaremos cada paso en detalle.

Ordenación de matrices

Empecemos por la parte fácil. La idea básica del algoritmo es dividir (sub) matrices en mitades y ordenarlas de forma recursiva. Queremos seguir haciendo esto tanto como sea posible, es decir, hasta que terminemos con subarreglos que solo tengan un elemento:

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)

Llamando al merge último método, nos aseguramos de que todas las divisiones ocurran antes de comenzar la clasificación. Usamos el // operador sea explícito 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:

  • Cree 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), seleccionando el más pequeño de los dos elementos que estamos viendo actualmente y los agregamos a nuestra matriz ordenada. Avanzamos en la matriz de la que hemos 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, sigamos adelante y definamos un merge() función:

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:

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:

[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 el __eq__, __le__, __ge__ y otros operadores según sea necesario para esto.

Esto nos permite usar el mismo algoritmo 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 agregue algunos campos:

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 sencilla de lograr lo que queremos es utilizando 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:

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 algunos Car instancias:

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:

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

Mejoramiento

Elaboremos ahora la diferencia entre la clasificación por fusión de arriba hacia abajo y de abajo hacia arriba. De abajo hacia arriba funciona como la segunda mitad del enfoque de arriba hacia abajo, donde en lugar de llamar de forma recursiva al ordenamiento en subarreglos divididos a 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 pueden estar ya ordenados: {4,8}, {7}, {2,11}, {1,3}, y luego ordenándolos.

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 multihilo. 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 ordenar 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 llegamos a una matriz de ~ 7 elementos, en lugar de bajar a matrices con un elemento y llamar a Insertion Sort 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 matrices pequeñas y / o casi ordenadas.

Conclusión

Merge Sort es un algoritmo de clasificación eficaz y de uso general. Su principal ventaja es el tiempo de ejecución confiable del algoritmo y su eficiencia al clasificar arreglos grandes. A diferencia de Quick Sort, no depende de decisiones desafortunadas que conduzcan 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 conquistar para la creación de 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.

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad