Clasificación de algoritmos en Python

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 utilizarlos de manera eficiente...

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, veremos algoritmos de clasificación populares, comprenderemos cómo funcionan y los codificaremos en Python. También compararemos la rapidez con la que ordenan los elementos de una lista.

Para simplificar, las implementaciones de algoritmos clasificarían listas de números en orden ascendente. Por supuesto, eres libre de adaptarlos a tus necesidades.

Clasificación por burbujas {#clasificación por burbujas}

Este algoritmo de clasificación simple itera sobre una lista, comparando elementos en pares e intercambiándolos hasta que los elementos más grandes “suben” al final de la lista, y los elementos más pequeños permanecen en el “fondo”.

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 de la lista.

Al llegar al final de la lista, repite este proceso para cada elemento. Sin embargo, esto es altamente ineficiente. ¿Qué sucede si solo se necesita realizar un único intercambio en la matriz? ¿Por qué seguiríamos iterando n^2 veces, aunque ya está ordenado?

Obviamente, para optimizar el algoritmo, debemos detenerlo cuando termine de ordenar, de lo contrario, volverá a evaluar 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 cambiar ninguno. Entonces, cada vez que intercambiamos valores, establecemos un indicador en Verdadero para repetir el proceso de clasificación. Si no ocurrieron intercambios, la bandera permanecería en Falso y el algoritmo se detendría.

Si desea leer un artículo más detallado y dedicado sobre Clasificación de burbujas, ¡lo tenemos cubierto!

Implementación

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 ciclo “while”, y solo se interrumpe cuando no se intercambian elementos. Establecemos swapped en True al principio para garantizar que el algoritmo se ejecute 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 bandera ‘intercambiada’ se establecería en ‘Verdadero’ en cada iteración.

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

Clasificación 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 ordenado 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 se reitera hasta que el último elemento de la lista es el elemento restante a examinar.

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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 aumenta i, necesitamos verificar menos elementos.

Complejidad del tiempo

Podemos obtener fácilmente la complejidad del tiempo examinando los bucles for en el algoritmo de ordenación por 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 a Selection Sort una complejidad de tiempo de O(n^2).

Clasificación por inserción

Al igual que la clasificación por selección, este algoritmo segmenta la lista en partes ordenadas y no ordenadas. Itera sobre el segmento no ordenado 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 x. Si x es mayor que el primer elemento, lo dejamos como está. Si x es menor, copiamos el valor del primer elemento a la segunda posición y luego establecemos el primer elemento en x.

A medida que vamos a los otros elementos del segmento sin ordenar, 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 que x o llegamos al final del segmento ordenado, y luego colocamos x en es la posición correcta.

Si desea leer un artículo detallado y dedicado a Tipo de inserción, ¡lo tenemos cubierto!

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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 ‘bucle for’ externo en la función Ordenar por inserción siempre itera n-1 veces.

En el peor de los casos, el ‘bucle for’ interno se intercambiaría una vez, luego intercambiaría dos y así sucesivamente. La cantidad de intercambios sería 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1) lo que le da a la ordenación por inserción una complejidad de tiempo de O(n^2) ).

Clasificación en montón {#clasificación en montón}

Este popular algoritmo de ordenación, al igual que las ordenaciones por inserción y selección, segmenta la lista en partes ordenadas y no ordenadas. Convierte el segmento no ordenado de la lista en una estructura de datos Heap, para que podamos determinar de manera eficiente el elemento más grande.

Explicación

Comenzamos transformando la lista en Max Heap: un árbol binario donde el elemento más grande es el nodo 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.

Iteramos este proceso de construcción del montón hasta que se eliminen todos los nodos.

Si desea leer un artículo detallado y dedicado a Ordenar montón, ¡lo tenemos cubierto!

Implementación

Crearemos una función auxiliar heapify para implementar este algoritmo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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 función heapify. En el peor de los casos, el elemento más grande nunca es el elemento raíz, lo que provoca una llamada recursiva a heapify. Si bien las llamadas recursivas pueden parecer abrumadoramente costosas, 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 hasta n. La función heapify atraviesa ese árbol en O(log(n)) tiempo.

La función heap_sort itera sobre la matriz n veces. Por lo tanto, la complejidad de tiempo general del algoritmo Heap Sort es O(nlog(n)).

Clasificación por combinación

Este algoritmo divide y vencerás 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 fusionan y ordenan 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 ordenar.

Explicación

Dividimos recursivamente 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. Los primeros elementos de cada lista son los primeros en ser comparados. Si la primera mitad comienza con un valor menor, 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 un medio, movemos el índice de qué elemento debe compararse en uno.

Si desea leer un artículo detallado y dedicado a Ordenar por combinación, ¡lo tenemos cubierto!

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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 función merge_sort(), a diferencia de los algoritmos de clasificación anteriores, devuelve una nueva lista que está ordenada, en lugar de clasificar 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 función merge. Toma dos listas e itera n veces, donde n es el tamaño de su entrada combinada.

La función merge_sort divide su matriz dada en 2 y ordena recursivamente las sub-matrices. Como la entrada que se recurre es la mitad de lo que se proporcionó, como los árboles binarios, esto hace que el tiempo que lleva procesar crezca logarítmicamente a * n *.

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

Clasificación rápida {#clasificación rápida}

Este algoritmo divide y vencerás es el algoritmo de clasificación más utilizado que se trata en este artículo. Cuando se configura correctamente, es extremadamente eficiente y no requiere el espacio adicional que utiliza Merge Sort. Dividimos la lista alrededor de un elemento pivote, ordenando los valores alrededor del pivote.

Explicación

Quick Sort comienza dividiendo la lista: seleccionando 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 a Ordenación rápida, ¡lo tenemos cubierto!

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 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 terribles, Quick Sort se usa mucho porque su complejidad de tiempo promedio es mucho más rápida. Si bien la función partición utiliza bucles while anidados, realiza 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 crecen logarítmicamente con n. Por lo tanto, la complejidad de tiempo promedio del algoritmo Quick Sort es O(nlog(n)).

Funciones de clasificació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 ordenar su contenido con el método sort():

1
2
3
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 función sorted() para crear una nueva lista ordenada:

1
2
3
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 ordenan en orden ascendente, pero puedes ordenar fácilmente en orden descendente configurando el indicador reverse en True:

1
2
3
4
5
6
7
# 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 función sorted() puede ordenar cualquier objeto iterable y eso incluye: listas, cadenas, tuplas, diccionarios, conjuntos y iteradores personalizados que puede crear.

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

Comparaciones de velocidad {#comparaciones de velocidad}

Para tener una idea de qué tan rápido 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 es en segundos:

Ejecutar selección de burbuja Inserción Heap Merge Quick


1 5,53188 1,23152 1,60355 0,04006 0,02619 0,01639 2 4,92176 1,24728 1,59103 0,03999 0,02584 0,01661 3 4,91642 1,22440 1,59362 0,04407 0,02862 0,01646 4 5,15470 1,25053 1,63463 0,04128 0,02882 0,01860 5 4,95522 1,28987 1,61759 0,04515 0,03314 0,01885 6 5,04907 1,25466 1,62515 0,04257 0,02595 0,01628 7 5,05591 1,24911 1,61981 0,04028 0,02733 0,01760 8 5,08799 1,25808 1,62603 0,04264 0,02633 0,01705 9 5,03289 1,24915 1,61446 0,04302 0,03293 0,01762 10 5,14292 1,22021 1,57273 0,03966 0,02572 0,01606 Promedio 5.08488 1.24748 1.60986 0.04187 0.02809 0.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 desempeño 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 el doble de rápido que Merge Sort y no necesitaría tanto espacio para ejecutarse. 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 muchas menos comparaciones 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.

Las ordenaciones por inserción hacen muchos más intercambios que las ordenaciones por selección. Si intercambiar valores toma mucho más tiempo que comparar 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. Examinamos 6 algoritmos diferentes: clasificación de burbuja, 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 las aplicaciones reales de Python, se recomienda que nos apeguemos a las funciones de clasificación integradas de Python por su flexibilidad en la entrada y la velocidad.