Combinar ordenar en Python

    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.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *