Breaking

Post Top Ad

Your Ad Spot

viernes, 14 de junio de 2019

Ordenando los algoritmos 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 científicos informáticos han creado muchos algoritmos de clasificación para organizar los datos.
En este artículo analizaremos los algoritmos de clasificación populares, entenderemos cómo funcionan y codificarlos en Python. También compararemos la rapidez con la que ordenan los elementos en una lista.
Para simplificar, 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 saltar aquí:

Ordenamiento de burbuja

Este sencillo algoritmo de clasificación recorre una lista, compara los elementos en pares y los intercambia 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 elemento, 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 en la lista.
Al llegar al final de la lista, repite este proceso para cada elemento. Sin embargo, esto es altamente ineficiente. ¿Qué pasa si solo se necesita hacer un único intercambio en la matriz? ¿Por qué todavía iteraríamos si n ^ 2 veces, aunque ya esté ordenado?
Obviamente, para optimizar el algoritmo, debemos detenerlo cuando haya terminado de clasificar.
¿Cómo sabríamos que hemos terminado de clasificar? Si los artículos estuvieran en orden, no tendríamos que intercambiarlos. Por lo tanto, cada vez que intercambiamos valores, establecemos una marca Truepara repetir el proceso de clasificación. Si no ocurrieran swaps, la bandera permaneceríaFalse y el algoritmo se detendrá.

Implementación

Con la optimización, podemos implementar la ordenación de burbujas 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. Nos pusimos swappedaTrue en un principio para asegurar que el algoritmo se ejecuta 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 cada elemento de la matriz. Nuestra swappedbandera se pondrí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 del tiempo de Bubble Sort es O (n ^ 2) .

Selección de selección

Este algoritmo segmenta la lista en dos partes: ordenada y sin clasificar. Eliminamos continuamente el elemento más pequeño del segmento sin clasificar 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 la lista completa 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 se repite hasta que el último elemento de la lista es el elemento restante que se 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 tener que revisar menos artículos.

Complejidad del tiempo

Podemos obtener fácilmente la complejidad del tiempo mediante el examen de los forbucles en el algoritmo de selección por selección. Para una lista con n elementos, el bucle externo se repite nveces. El bucle interno itera n-1 cuando i es igual a 1, y luego n-2 como i es igual a 2 y así sucesivamente.
La cantidad de comparaciones es (n - 1) + (n - 2) + ... + 1, lo que le da a la Ordenación por selección una complejidad de tiempo de O (n ^ 2) .

Tipo de inserción

Al igual que el ordenamiento por selección, este algoritmo divide la lista en partes ordenadas y no clasificadas. Recorre el segmento sin clasificar e inserta el elemento que se está viendo en la posición correcta de la lista ordenada.

Explicación

Suponemos que el primer elemento de la lista está ordenado. Luego vamos al siguiente elemento, llamémoslo xSi xes más grande que el primer elemento lo dejamos como está. Si xes más pequeño, copiamos el valor del primer elemento a la segunda posición y luego establecemos el primer elemento enx .
A medida que avanzamos hacia los otros elementos del segmento no clasificado, movemos continuamente los elementos más grandes en el segmento ordenado hacia arriba en la lista hasta que encontramos un elemento más pequeño xo que llegamos al final del segmento ordenado, y luego lo colocamos xen su posición correcta.

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 de inserción siempre itera n-1 veces.
En el peor de los casos, el bucle for interno se intercambiaría una vez, luego cambiaría dos y así sucesivamente. La cantidad de swaps sería entonces lo 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1)que le da a la Inserción una complejidad de tiempo de O (n ^ 2) .

Heap Sort

Este popular algoritmo de clasificación, como la clasificación de Inserción y Selección, divide la lista en partes clasificadas y no clasificadas. Convierte el segmento no clasificado 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 nodo raíz. A continuación, 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.
Recorremos este proceso de compilación hasta que se eliminen todos los nodos.

Implementación

Creamos 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 heapifySi bien las llamadas recursivas pueden parecer tremendamente caras, recuerde que estamos trabajando con un árbol binario.
Visualice un árbol binario con 3 elementos, tiene una altura de 2. Ahora visualice un árbol binario con 7 elementos, tiene una altura de 3. El árbol crece logarítmicamente a n . 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 global del algoritmo de ordenación de pila es O (nlog (n)) .

Fusionar clasificación

Este algoritmo de dividir y conquistar divide una lista a la mitad y sigue dividiendo la lista en 2 hasta que solo tenga elementos singulares.
Los elementos adyacentes se convierten en pares ordenados, luego los pares ordenados se combinan y también se ordenan 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 la lista recursivamente a la mitad hasta que tengamos listas con el tamaño uno. Luego fusionamos cada mitad que se dividió, ordenándolos 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 menor, entonces 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.

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 clasificación anteriores, devuelve una nueva lista que está 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

Veamos primero 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 subarreglas. Como la entrada que se recurre es la mitad de lo que se proporcionó, como los árboles binarios, esto hace que el tiempo que toma procesar crezca logarítmicamente a n .
Por lo tanto, la complejidad de tiempo total del algoritmo de clasificación de mezcla es O (nlog (n)) .

Ordenación rápida

Este algoritmo de dividir y conquistar es el algoritmo de clasificación más utilizado en este artículo. Cuando se configura correctamente, es extremadamente eficiente y no requiere el espacio extra que utiliza la Ordenación de mezcla. Particionamos la lista en torno a un elemento de pivote, ordenando los valores en torno al pivote.

Explicación

La clasificación rápida comienza dividiendo la lista, seleccionando un valor de la lista que estará en su lugar ordenado. Este valor se llama un 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 clasifique la lista completa.

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 el pivote. Esto crearía particiones de tamaño n-1 , causando llamadas recursivas n-1 veces. Esto nos lleva a una complejidad en el peor de los casos de O (n ^ 2) .
Si bien este es el peor de los casos, Quick Sort se usa mucho porque la complejidad del tiempo promedio es mucho más rápida. Mientras que la partitionfunción utiliza bucles while anidados, hace comparaciones en todos los elementos de la matriz para hacer sus swaps. Como tal, tiene una complejidad de tiempo de O (n) .
Con un buen pivote, la función de ordenación rápida dividiría la matriz en mitades que crecen logarítmicamente con n . Por lo tanto, la complejidad de tiempo promedio del algoritmo de ordenaciónrápida es O (nlog (n)) .

Funciones de ordenación incorporadas de Python

Si bien es beneficioso entender estos algoritmos de clasificación, en la mayoría de los proyectos de Python, probablemente utilice las funciones de clasificación que ya se encuentran en el lenguaje.
Podemos cambiar nuestra lista para que su contenido se clasifique según 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 clasifican en orden ascendente, pero puede ordenar fácilmente en orden descendente si establece 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 clasificación que creamos, ambas funciones pueden ordenar listas de tuplas y clases. La sorted()función puede ordenar cualquier objeto iterable, que incluye: listas, cadenas, tuplas, diccionarios, conjuntos e iteradores personalizados que puede crear.
Estas funciones de clasificación implementan el algoritmo de clasificación de Tim , un algoritmo inspirado en la clasificación de combinación y la clasificación de inserción.

Comparaciones de velocidad

Para tener una idea de qué tan rápido se desempeñan, 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 rendimiento.
Estos fueron los resultados, el tiempo es en segundos:
correrBurbujaSelecciónInserciónMontónUnirRápido
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
Avg5.084881.247481.609860.041870.028090.01715
Obtendría diferentes valores si configura la prueba usted mismo, pero los patrones observados deben ser iguales o similares. Bubble Sort es el más lento y el peor de todos los algoritmos. Si bien es útil como introducción a la clasificación y los algoritmos, no es adecuado para el uso práctico.
También notamos que la clasificación rápida es muy rápida, casi el doble que la combinación de clasificación y no necesitaría tanto espacio para ejecutar. Recuerde que nuestra partición se basó en el elemento central de la lista, diferentes particiones podrían tener diferentes resultados.
Como la ordenación por inserción realiza comparaciones mucho menos que la ordenación por selección, las implementaciones suelen ser más rápidas, pero en estas ejecuciones, la ordenación por selección es un poco más rápida.
Los ordenamientos de inserción hacen muchos más intercambios que el ordenamiento por selección. Si el intercambio de valores toma considerablemente más tiempo que la comparación de valores, 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 ordenación nos ofrecen muchas formas de ordenar nuestros datos. Nos fijamos en 6 algoritmos diferentes (ordenamiento de burbuja, ordenamiento de selección, ordenamiento de inserción, ordenamiento de combinación, ordenamiento de pila, ordenamiento rápido) y sus implementaciones en Python.
La cantidad de comparaciones e intercambios que realiza el algoritmo junto con el entorno que ejecuta el código son determinantes clave del rendimiento. En aplicaciones reales de Python, se recomienda mantener las funciones de ordenamiento Python integradas por su flexibilidad en la entrada y la velocidad.

No hay comentarios.:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Post Top Ad

Your Ad Spot

Páginas