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

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.