Algoritmos de ordenaci贸n en Python

    Introducci贸n

    A veces, los datos que almacenamos o recuperamos en una aplicaci贸n pueden tener poco o ning煤n orden. Es posible que tengamos que reorganizar los datos para procesarlos correctamente o usarlos de manera eficiente. A lo largo de los a帽os, los inform谩ticos han creado muchos algoritmos de clasificaci贸n para organizar los datos.

    En este art铆culo, echaremos un vistazo a los algoritmos de clasificaci贸n populares, entenderemos c贸mo funcionan y los codificaremos en Python. Tambi茅n compararemos la rapidez con la que clasifican los elementos de una lista.

    Por simplicidad, las implementaciones de algoritmos ser铆an ordenar listas de n煤meros en orden ascendente. Por supuesto, eres libre de adaptarlos a tus necesidades.

    Si desea obtener informaci贸n sobre un algoritmo espec铆fico, puede acceder a 茅l aqu铆:

    • Ordenamiento de burbuja
    • Orden de selecci贸n
    • Tipo de inserci贸n
    • Combinar ordenar
    • Ordenar mont贸n
    • Ordenaci贸n r谩pida
    • Ordenar en Python

    Ordenamiento de burbuja

    Este simple algoritmo de clasificaci贸n itera sobre una lista, comparando elementos en pares e intercambi谩ndolos hasta que los elementos m谩s grandes “burbujean” hasta el final de la lista, y los elementos m谩s peque帽os permanecen en la “parte inferior”.

    Explicaci贸n

    Comenzamos comparando los dos primeros elementos de la lista. Si el primer elemento es m谩s grande que el segundo, los intercambiamos. Si ya est谩n en orden los dejamos como est谩n. Luego pasamos al siguiente par de elementos, comparamos sus valores e intercambiamos seg煤n sea necesario. Este proceso contin煤a hasta el 煤ltimo par de elementos de la lista.

    Al llegar al final de la lista, repite este proceso para cada elemento. Sin embargo, esto es muy ineficiente. 驴Qu茅 pasa si solo se necesita hacer un 煤nico intercambio en la matriz? 驴Por qu茅 seguir铆amos iterando aunque n ^ 2 veces, aunque ya est茅 ordenado?

    Obviamente, para optimizar el algoritmo, debemos detenerlo cuando termine de ordenar, de lo contrario reevaluar谩 una matriz ya ordenada muchas veces.

    驴C贸mo sabr铆amos que hemos terminado de clasificar? Si los art铆culos estuvieran en orden, no tendr铆amos que cambiarlos. Entonces, cada vez que intercambiamos valores, establecemos una bandera Truepara repetir el proceso de clasificaci贸n. Si no se produjeron intercambios, la bandera permanecer铆a Falsey el algoritmo se detendr谩.

    Implementaci贸n

    Con la optimizaci贸n, podemos implementar Bubble Sort en Python de la siguiente manera:

    def bubble_sort(nums):
        # We set swapped to True so the loop looks runs at least once
        swapped = True
        while swapped:
            swapped = False
            for i in range(len(nums) - 1):
                if nums[i] > nums[i + 1]:
                    # Swap the elements
                    nums[i], nums[i + 1] = nums[i + 1], nums[i]
                    # Set the flag to True so we'll loop again
                    swapped = True
    
    
    # Verify it works
    random_list_of_nums = [5, 2, 1, 8, 4]
    bubble_sort(random_list_of_nums)
    print(random_list_of_nums)
    

    El algoritmo se ejecuta en un whilebucle, solo se rompe cuando no se intercambian elementos. Hemos establecido swappedque Trueen un principio para asegurar que se ejecuta el algoritmo al menos una vez.

    Complejidad del tiempo

    En el peor de los casos (cuando la lista est谩 en orden inverso), este algoritmo tendr铆a que intercambiar todos los elementos de la matriz. Nuestra swappedbandera se establecer铆a Trueen cada iteraci贸n.

    Por lo tanto, si tenemos n elementos en nuestra lista, tendr铆amos n iteraciones por elemento, por lo que la complejidad de tiempo de Bubble Sort es O (n ^ 2) .

    Orden de selecci贸n

    Este algoritmo segmenta la lista en dos partes: ordenada y no ordenada. Eliminamos continuamente el elemento m谩s peque帽o del segmento no clasificado de la lista y lo agregamos al segmento ordenado.

    Explicaci贸n

    En la pr谩ctica, no necesitamos crear una nueva lista para los elementos ordenados, lo que hacemos es tratar la parte m谩s a la izquierda de la lista como el segmento ordenado. Luego buscamos en toda la lista el elemento m谩s peque帽o y lo intercambiamos con el primer elemento.

    Ahora que sabemos que el primer elemento de la lista est谩 ordenado, obtenemos el elemento m谩s peque帽o de los elementos restantes y lo intercambiamos con el segundo elemento. Esto reitera hasta que el 煤ltimo elemento de la lista es el elemento restante por examinar.

    Implementaci贸n

    def selection_sort(nums):
        # This value of i corresponds to how many values were sorted
        for i in range(len(nums)):
            # We assume that the first item of the unsorted segment is the smallest
            lowest_value_index = i
            # This loop iterates over the unsorted items
            for j in range(i + 1, len(nums)):
                if nums[j] < nums[lowest_value_index]:
                    lowest_value_index = j
            # Swap values of the lowest unsorted element with the first unsorted
            # element
            nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i]
    
    
    # Verify it works
    random_list_of_nums = [12, 8, 3, 20, 11]
    selection_sort(random_list_of_nums)
    print(random_list_of_nums)
    

    Vemos que a medida que iaumenta, necesitamos verificar menos elementos.

    Complejidad del tiempo

    Podemos obtener f谩cilmente la complejidad del tiempo examinando los forbucles en el algoritmo de clasificaci贸n de selecci贸n. Para una lista con n elementos, el ciclo externo itera n veces.

    El ciclo interno itera n-1 cuando i es igual a 1, y luego n-2 cuando i es igual a 2 y as铆 sucesivamente.

    La cantidad de comparaciones es (n - 1) + (n - 2) + ... + 1, lo que le da al Orden de selecci贸n una complejidad de tiempo de O (n ^ 2) .

    Tipo de inserci贸n

    Al igual que el ordenamiento por selecci贸n, este algoritmo segmenta la lista en partes ordenadas y no ordenadas. Repite el segmento sin clasificar e inserta el elemento que se est谩 visualizando en la posici贸n correcta de la lista ordenada.

    Explicaci贸n

    Suponemos que el primer elemento de la lista est谩 ordenado. Luego pasamos al siguiente elemento, llam茅moslo x. Si xes mayor que el primer elemento lo dejamos como est谩. Si xes m谩s peque帽o, copiamos el valor del primer elemento en la segunda posici贸n y luego establecemos el primer elemento en x.

    A medida que avanzamos hacia los otros elementos del segmento sin clasificar, continuamente movemos elementos m谩s grandes en el segmento ordenado hacia arriba en la lista hasta que encontramos un elemento m谩s peque帽o xo llegamos al final del segmento ordenado, y luego lo colocamos xen su posici贸n correcta.

    Si desea leer un art铆culo detallado y dedicado para el ordenamiento por inserci贸n, 隆lo tenemos cubierto!

    Implementaci贸n

    def insertion_sort(nums):
        # Start on the second element as we assume the first element is sorted
        for i in range(1, len(nums)):
            item_to_insert = nums[i]
            # And keep a reference of the index of the previous element
            j = i - 1
            # Move all items of the sorted segment forward if they are larger than
            # the item to insert
            while j >= 0 and nums[j] > item_to_insert:
                nums[j + 1] = nums[j]
                j -= 1
            # Insert the item
            nums[j + 1] = item_to_insert
    
    
    # Verify it works
    random_list_of_nums = [9, 1, 15, 28, 6]
    insertion_sort(random_list_of_nums)
    print(random_list_of_nums)
    

    Complejidad del tiempo

    En el peor de los casos, una matriz se ordenar铆a en orden inverso. El exterior for loopen la funci贸n de ordenaci贸n por inserci贸n siempre itera n-1 veces.

    En el peor de los casos, el interior for loopcambiar铆a una vez, luego cambiar铆a dos y as铆 sucesivamente. La cantidad de intercambios ser铆a entonces lo 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1)que le da a Insertion Sort una complejidad de tiempo de O (n ^ 2) .

    Ordenar mont贸n

    Este popular algoritmo de clasificaci贸n, como los tipos de inserci贸n y selecci贸n, segmenta la lista en partes ordenadas y no ordenadas. Convierte el segmento sin clasificar de la lista en una estructura de datos Heap, para que podamos determinar de manera eficiente el elemento m谩s grande.

    Explicaci贸n

    Comenzamos por transformar la lista en un mont贸n m谩ximo , un 谩rbol binario donde el elemento m谩s grande es el node ra铆z. Luego colocamos ese elemento al final de la lista. Luego reconstruimos nuestro Max Heap, que ahora tiene un valor menos, colocando el nuevo valor m谩s grande antes del 煤ltimo elemento de la lista.

    Repetimos este proceso de construcci贸n del mont贸n hasta que se eliminan todos los nodes.

    Si desea leer un art铆culo detallado y dedicado para Heap Sort, 隆lo tenemos cubierto!

    Implementaci贸n

    Crearemos una funci贸n auxiliar heapifypara implementar este algoritmo:

    def heapify(nums, heap_size, root_index):
        # Assume the index of the largest element is the root index
        largest = root_index
        left_child = (2 * root_index) + 1
        right_child = (2 * root_index) + 2
    
        # If the left child of the root is a valid index, and the element is greater
        # than the current largest element, then update the largest element
        if left_child < heap_size and nums[left_child] > nums[largest]:
            largest = left_child
    
        # Do the same for the right child of the root
        if right_child < heap_size and nums[right_child] > nums[largest]:
            largest = right_child
    
        # If the largest element is no longer the root element, swap them
        if largest != root_index:
            nums[root_index], nums[largest] = nums[largest], nums[root_index]
            # Heapify the new root element to ensure it's the largest
            heapify(nums, heap_size, largest)
    
    
    def heap_sort(nums):
        n = len(nums)
    
        # Create a Max Heap from the list
        # The 2nd argument of range means we stop at the element before -1 i.e.
        # the first element of the list.
        # The 3rd argument of range means we iterate backwards, reducing the count
        # of i by 1
        for i in range(n, -1, -1):
            heapify(nums, n, i)
    
        # Move the root of the max heap to the end of
        for i in range(n - 1, 0, -1):
            nums[i], nums[0] = nums[0], nums[i]
            heapify(nums, i, 0)
    
    
    # Verify it works
    random_list_of_nums = [35, 12, 43, 8, 51]
    heap_sort(random_list_of_nums)
    print(random_list_of_nums)
    

    Complejidad del tiempo

    Veamos primero la complejidad temporal de la heapifyfunci贸n. En el peor de los casos, el elemento m谩s grande nunca es el elemento ra铆z, esto provoca una llamada recursiva a heapify. Si bien las llamadas recursivas pueden parecer abrumadoramente caras, recuerde que estamos trabajando con un 谩rbol binario.

    Visualiza un 谩rbol binario con 3 elementos, tiene una altura de 2. Ahora visualiza un 谩rbol binario con 7 elementos, tiene una altura de 3. El 谩rbol crece logar铆tmicamente an. La heapifyfunci贸n atraviesa ese 谩rbol en tiempo O (log (n)) .

    La heap_sortfunci贸n itera sobre la matriz n veces. Por lo tanto, la complejidad de tiempo total del algoritmo de clasificaci贸n de mont贸n es O (nlog (n)) .

    Combinar ordenar

    Este algoritmo de dividir y conquistar divide una lista por la mitad y sigue dividiendo la lista por 2 hasta que solo tiene elementos singulares.

    Los elementos adyacentes se convierten en pares ordenados, luego los pares ordenados se combinan y clasifican tambi茅n con otros pares. Este proceso contin煤a hasta que obtenemos una lista ordenada con todos los elementos de la lista de entrada sin clasificar.

    Explicaci贸n

    Dividimos de forma recursiva la lista por la mitad hasta que tengamos listas de tama帽o uno. Luego fusionamos cada mitad que se dividi贸, clasific谩ndolas en el proceso.

    La clasificaci贸n se realiza comparando los elementos m谩s peque帽os de cada mitad. El primer elemento de cada lista son los primeros en ser comparados. Si la primera mitad comienza con un valor m谩s peque帽o, lo agregamos a la lista ordenada. Luego comparamos el segundo valor m谩s peque帽o de la primera mitad con el primer valor m谩s peque帽o de la segunda mitad.

    Cada vez que seleccionamos el valor m谩s peque帽o al comienzo de la mitad, movemos el 铆ndice de qu茅 elemento debe compararse en uno.

    Si desea leer un art铆culo detallado y dedicado a Merge Sort, 隆lo tenemos cubierto!

    Implementaci贸n

    def merge(left_list, right_list):
        sorted_list = []
        left_list_index = right_list_index = 0
    
        # We use the list lengths often, so its handy to make variables
        left_list_length, right_list_length = len(left_list), len(right_list)
    
        for _ in range(left_list_length + right_list_length):
            if left_list_index < left_list_length and right_list_index < right_list_length:
                # We check which value from the start of each list is smaller
                # If the item at the beginning of the left list is smaller, add it
                # to the sorted list
                if left_list[left_list_index] <= right_list[right_list_index]:
                    sorted_list.append(left_list[left_list_index])
                    left_list_index += 1
                # If the item at the beginning of the right list is smaller, add it
                # to the sorted list
                else:
                    sorted_list.append(right_list[right_list_index])
                    right_list_index += 1
    
            # If we've reached the end of the of the left list, add the elements
            # from the right list
            elif left_list_index == left_list_length:
                sorted_list.append(right_list[right_list_index])
                right_list_index += 1
            # If we've reached the end of the of the right list, add the elements
            # from the left list
            elif right_list_index == right_list_length:
                sorted_list.append(left_list[left_list_index])
                left_list_index += 1
    
        return sorted_list
    
    
    def merge_sort(nums):
        # If the list is a single element, return it
        if len(nums) <= 1:
            return nums
    
        # Use floor division to get midpoint, indices must be integers
        mid = len(nums) // 2
    
        # Sort and merge each half
        left_list = merge_sort(nums[:mid])
        right_list = merge_sort(nums[mid:])
    
        # Merge the sorted lists into a new one
        return merge(left_list, right_list)
    
    
    # Verify it works
    random_list_of_nums = [120, 45, 68, 250, 176]
    random_list_of_nums = merge_sort(random_list_of_nums)
    print(random_list_of_nums)
    

    Tenga en cuenta que la merge_sort()funci贸n, a diferencia de los algoritmos de ordenaci贸n anteriores, devuelve una nueva lista ordenada, en lugar de ordenar la lista existente.

    Por lo tanto, Merge Sort requiere espacio para crear una nueva lista del mismo tama帽o que la lista de entrada.

    Complejidad del tiempo

    Primero veamos la mergefunci贸n. Toma dos listas e itera n veces, donde n es el tama帽o de su entrada combinada.

    La merge_sortfunci贸n divide su matriz dada en 2 y ordena recursivamente las submatrices. Como la entrada que se repite es la mitad de lo que se dio, al igual que los 谩rboles binarios, esto hace que el tiempo que se tarda en procesar crezca logar铆tmicamente hasta n.

    Por lo tanto, la complejidad de tiempo total del algoritmo Merge Sort es O (nlog (n)) .

    Ordenaci贸n r谩pida

    Este algoritmo de divide y vencer谩s es el algoritmo de clasificaci贸n m谩s utilizado que se cubre en este art铆culo. Cuando se configura correctamente, es extremadamente eficiente y no requiere el espacio adicional que usa Merge Sort. Particionamos la lista alrededor de un elemento pivote, ordenando los valores alrededor del pivote.

    Explicaci贸n

    La clasificaci贸n r谩pida comienza dividiendo la lista, eligiendo un valor de la lista que estar谩 en su lugar ordenado. Este valor se llama pivote. Todos los elementos m谩s peque帽os que el pivote se mueven a su izquierda. Todos los elementos m谩s grandes se mueven a su derecha.

    Sabiendo que el pivote est谩 en el lugar que le corresponde, ordenamos recursivamente los valores alrededor del pivote hasta que se ordena toda la lista.

    Si desea leer un art铆culo detallado y dedicado para la clasificaci贸n r谩pida, 隆lo tenemos cubierto!

    Implementaci贸n

    # There are different ways to do a Quick Sort partition, this implements the
    # Hoare partition scheme. Tony Hoare also created the Quick Sort algorithm.
    def partition(nums, low, high):
        # We select the middle element to be the pivot. Some implementations select
        # the first element or the last element. Sometimes the median value becomes
        # the pivot, or a random one. There are many more strategies that can be
        # chosen or created.
        pivot = nums[(low + high) // 2]
        i = low - 1
        j = high + 1
        while True:
            i += 1
            while nums[i] < pivot:
                i += 1
    
            j -= 1
            while nums[j] > pivot:
                j -= 1
    
            if i >= j:
                return j
    
            # If an element at i (on the left of the pivot) is larger than the
            # element at j (on right right of the pivot), then swap them
            nums[i], nums[j] = nums[j], nums[i]
    
    
    def quick_sort(nums):
        # Create a helper function that will be called recursively
        def _quick_sort(items, low, high):
            if low < high:
                # This is the index after the pivot, where our lists are split
                split_index = partition(items, low, high)
                _quick_sort(items, low, split_index)
                _quick_sort(items, split_index + 1, high)
    
        _quick_sort(nums, 0, len(nums) - 1)
    
    
    # Verify it works
    random_list_of_nums = [22, 5, 1, 18, 99]
    quick_sort(random_list_of_nums)
    print(random_list_of_nums)
    

    Complejidad del tiempo

    El peor de los casos es cuando el elemento m谩s peque帽o o m谩s grande siempre se selecciona como pivote. Esto crear铆a particiones de tama帽o n-1, provocando llamadas recursivas n-1 veces. Esto nos lleva a una complejidad temporal en el peor de los casos de O (n ^ 2) .

    Si bien este es el peor de los casos, la clasificaci贸n r谩pida se usa mucho porque su complejidad de tiempo promedio es mucho m谩s r谩pida. Si bien la partitionfunci贸n utiliza whilebucles anidados , hace comparaciones en todos los elementos de la matriz para realizar sus intercambios. Como tal, tiene una complejidad temporal de O (n) .

    Con un buen pivote, la funci贸n Quick Sort dividir铆a la matriz en mitades que crece logar铆tmicamente con n. Por lo tanto, la complejidad de tiempo promedio del algoritmo de clasificaci贸n r谩pida es O (nlog (n)) .

    Funciones de ordenaci贸n integradas de Python

    Si bien es beneficioso comprender estos algoritmos de clasificaci贸n, en la mayor铆a de los proyectos de Python probablemente usar铆a las funciones de clasificaci贸n ya proporcionadas en el lenguaje.

    Podemos cambiar nuestra lista para que su contenido se ordene con el sort()m茅todo:

    apples_eaten_a_day = [2, 1, 1, 3, 1, 2, 2]
    apples_eaten_a_day.sort()
    print(apples_eaten_a_day) # [1, 1, 1, 2, 2, 2, 3]
    

    O podemos usar la sorted()funci贸n para crear una nueva lista ordenada:

    apples_eaten_a_day_2 = [2, 1, 1, 3, 1, 2, 2]
    sorted_apples = sorted(apples_eaten_a_day_2)
    print(sorted_apples) # [1, 1, 1, 2, 2, 2, 3]
    

    Ambos se ordenan en orden ascendente, pero puede ordenar f谩cilmente en orden descendente configurando la reversebandera en True:

    # Reverse sort the list in-place
    apples_eaten_a_day.sort(reverse=True)
    print(apples_eaten_a_day) # [3, 2, 2, 2, 1, 1, 1]
    
    # Reverse sort to get a new list
    sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True)
    print(sorted_apples_desc) # [3, 2, 2, 2, 1, 1, 1]
    

    A diferencia de las funciones de algoritmo de ordenaci贸n que creamos, ambas funciones pueden ordenar listas de tuplas y clases. La sorted()funci贸n puede ordenar cualquier objeto iterable y eso incluye: listas, cadenas, tuplas, diccionarios, conjuntos e iteradores personalizados que puede crear.

    Estas funciones de clasificaci贸n implementan el algoritmo Tim Sort , un algoritmo inspirado en Merge Sort y Insertion Sort.

    Comparaciones de velocidad

    Para tener una idea de la rapidez con la que funcionan, generamos una lista de 5000 n煤meros entre 0 y 1000. Luego, calculamos el tiempo que tarda cada algoritmo en completarse. Esto se repite 10 veces para que podamos establecer de manera m谩s confiable un patr贸n de desempe帽o.

    Estos fueron los resultados, el tiempo est谩 en segundos:

    RunBubbleSelectionInsertionHeapMergeQuick

    15.531881.231521.603550.040060.026190.01639
    24.921761.247281.591030.039990.025840.01661
    34.916421.224401.593620.044070.028620.01646
    45.154701.250531.634630.041280.028820.01860
    54.955221.289871.617590.045150.033140.01885
    65.049071.254661.625150.042570.025950.01628
    75.055911.249111.619810.040280.027330.01760
    85.087991.258081.626030.042640.026330.01705
    95.032891.249151.614460.043020.032930.01762
    105.142921.220211.572730.039660.025720.01606
    Promedio5.084881.247481.609860.041870.028090.01715

    Obtendr谩 valores diferentes si configura la prueba usted mismo, pero los patrones observados deben ser iguales o similares. Bubble Sort es el m谩s lento y el de peor rendimiento de todos los algoritmos. Si bien es 煤til como introducci贸n a la clasificaci贸n y los algoritmos, no es adecuado para un uso pr谩ctico.

    Tambi茅n notamos que Quick Sort es muy r谩pido, casi dos veces m谩s r谩pido que Merge Sort y no necesitar铆a tanto espacio para ejecutarse. Recuerde que nuestra partici贸n se bas贸 en el elemento medio de la lista, diferentes particiones podr铆an tener diferentes resultados.

    Como el ordenamiento por inserci贸n realiza muchas menos comparaciones que el ordenamiento por selecci贸n, las implementaciones suelen ser m谩s r谩pidas, pero en estas ejecuciones el ordenamiento por selecci贸n es un poco m谩s r谩pido.

    Los ordenamientos por inserci贸n hacen muchos m谩s intercambios que el ordenamiento por selecci贸n. Si el intercambio de valores lleva considerablemente m谩s tiempo que la comparaci贸n de valores, entonces este resultado “contrario” ser铆a plausible.

    Tenga en cuenta el entorno al elegir su algoritmo de clasificaci贸n, ya que afectar谩 el rendimiento.

    Conclusi贸n

    Los algoritmos de clasificaci贸n nos brindan muchas formas de ordenar nuestros datos. Observamos 6 algoritmos diferentes: clasificaci贸n de burbujas, clasificaci贸n de selecci贸n, clasificaci贸n de inserci贸n, clasificaci贸n de combinaci贸n, clasificaci贸n de pila, clasificaci贸n r谩pida y sus implementaciones en Python.

    La cantidad de comparaciones e intercambios que realiza el algoritmo junto con el entorno en el que se ejecuta el c贸digo son determinantes clave del rendimiento. En aplicaciones reales de Python, se recomienda que nos quedemos con las funciones de ordenaci贸n de Python integradas por su flexibilidad en la entrada y la velocidad.

     

    Etiquetas:

    Deja una respuesta

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