Ordenar por cubos en Python

Introducción

En este tutorial, profundizaremos en la teoría y la implementación de Bucket Sort en Python.

Bucket Sort es un algoritmo de tipo de comparación que asigna elementos de una lista que queremos ordenar en Buckets o Bins. A continuación, se ordena el contenido de estos depósitos, normalmente con otro algoritmo. Después de ordenar, el contenido de los cubos se agrega, formando una colección ordenada.

La clasificación por cubos se puede considerar como un enfoque de dispersión, orden y recopilación para ordenar una lista, debido al hecho de que los elementos primero se dispersan en cubos, se ordenan dentro de ellos y finalmente se reúnen en una nueva lista ordenada.

Implementaremos Bucket Sort en Python y analizaremos su complejidad de tiempo.

¿Cómo funciona la clasificación por cubos?

Antes de pasar a su implementación exacta, repasemos los pasos del algoritmo:

• Configure una lista de depósitos vacíos. Se inicializa un depósito para cada elemento de la matriz.
• Repita la lista de deseos e inserte elementos de la matriz. El lugar donde se inserta cada elemento depende de la lista de entrada y del elemento más grande de la misma. Podemos terminar con 0..n elementos en cada cubo. Esto se desarrollará en la presentación visual del algoritmo.
• Clasifica cada balde que no esté vacío. Puede hacer esto con cualquier algoritmo de clasificación. Dado que estamos trabajando con un conjunto de datos pequeño, cada depósito no tendrá muchos elementos, por lo que Insertion Sort funciona de maravilla para nosotros aquí.
• Visite los cubos en orden. Una vez que se ordena el contenido de cada depósito, cuando se concatenan, producirán una lista en la que los elementos se organizan según sus criterios.

Echemos un vistazo a la presentación visual de cómo funciona el algoritmo. Por ejemplo, supongamos que esta es la lista de entrada:

El elemento más grande es 1.2, y la longitud de la lista es 6. Usando estos dos, averiguaremos el óptimo size de cada cubo. Obtendremos este número dividiendo el elemento más grande por la longitud de la lista. En nuestro caso, es 1.2/6 cual es 0.2.

Dividiendo el valor del elemento con este size, obtendremos un índice para el depósito respectivo de cada elemento.

Ahora crearemos depósitos vacíos. Tendremos la misma cantidad de depósitos que los elementos de nuestra lista:

Insertaremos los elementos en sus respectivos cubos. Teniendo en cuenta el primer elemento: 1.2/0.2 = 6, el índice de su respectivo segmento es 6. Si este resultado es mayor o igual a la longitud de la lista, simplemente restaremos 1 y encajará perfectamente en la lista. Esto solo sucede con el número más grande, ya que obtuvimos el size dividiendo el elemento más grande por la longitud.

Colocaremos este elemento en el depósito con el índice de 5:

Asimismo, el siguiente elemento se indexará a 0.22/0.2 = 1.1. Dado que este es un número decimal, lo nivelaremos. Esto se redondea a 1, y nuestro elemento se coloca en el segundo depósito:

Este proceso se repite hasta que hayamos colocado el último elemento en su respectivo depósito. Nuestros cubos ahora se ven algo así como:

Ahora, ordenaremos el contenido de cada cubo que no esté vacío. Usaremos el ordenamiento por inserción, ya que está invicto con listas pequeñas como esta. Después de la ordenación por inserción, los depósitos se ven así:

Ahora, es solo cuestión de atravesar los depósitos que no están vacíos y concatenar los elementos en una lista. Están ordenados y listos para usar:

Implementación de clasificación de cubos en Python

Con eso fuera del camino, sigamos adelante e implementemos el algoritmo en Python. Empecemos con el bucket_sort() función en sí misma:

def bucket_sort(input_list):
    # Find maximum value in the list and use length of the list to determine which value in the list goes into which bucket 
    max_value = max(input_list)
    size = max_value/len(input_list)

    # Create n empty buckets where n is equal to the length of the input list
    buckets_list= []
    for x in range(len(input_list)):
        buckets_list.append([]) 

    # Put list elements into different buckets based on the size
    for i in range(len(input_list)):
        j = int (input_list[i] / size)
        if j != len (input_list):
            buckets_list[j].append(input_list[i])
        else:
            buckets_list[len(input_list) - 1].append(input_list[i])

    # Sort elements within the buckets using Insertion Sort
    for z in range(len(input_list)):
        insertion_sort(buckets_list[z])
            
    # Concatenate buckets with sorted elements into a single list
    final_output = []
    for x in range(len (input_list)):
        final_output = final_output + buckets_list[x]
    return final_output

La implementación es bastante sencilla. Hemos calculado el size parámetro. Luego, instanciamos una lista de depósitos vacíos e insertamos elementos basados ​​en su valor y el size de cada cubo.

Una vez insertado, llamamos insertion_sort() en cada uno de los cubos:

def insertion_sort(bucket):
    for i in range (1, len (bucket)):
        var = bucket[i]
        j = i - 1
        while (j >= 0 and var < bucket[j]):
            bucket[j + 1] = bucket[j]
            j = j - 1
        bucket[j + 1] = var

Y con eso en su lugar, completemos una lista y realicemos una ordenación de cubos en ella:

def main():
    input_list = [1.20, 0.22, 0.43, 0.36,0.39,0.27]
    print('ORIGINAL LIST:')
    print(input_list)
    sorted_list = bucket_sort(input_list)
    print('SORTED LIST:')
    print(sorted_list)

Ejecutar este código devolverá:

Original list: [1.2, 0.22, 0.43, 0.36, 0.39, 0.27]
Sorted list: [0.22, 0.27, 0.36, 0.39, 0.43, 1.2]

Complejidad del tiempo de clasificación del segmento

Complejidad en el peor de los casos

Si la colección con la que estamos trabajando tiene un rango corto (como el que hemos tenido en nuestro ejemplo), es común tener muchos elementos en un solo depósito, donde muchos depósitos están vacíos.

Si todos los elementos caen en el mismo depósito, la complejidad depende exclusivamente del algoritmo que usemos para ordenar el contenido del propio depósito.

Dado que estamos usando la ordenación por inserción, su complejidad en el peor de los casos brilla cuando la lista está en orden inverso. Por lo tanto, la complejidad del peor de los casos para la clasificación de cubos también es O (n2).

Complejidad en el mejor de los casos

El mejor de los casos sería tener todos los elementos ya ordenados. Además, los elementos se distribuyen uniformemente. Esto significa que cada depósito tendría la misma cantidad de elementos.

Dicho esto, la creación de los depósitos tomaría O (n) y la ordenación por inserción tomaría O (k), lo que nos da una complejidad O (n + k).

Complejidad de casos promedio

El caso promedio ocurre en la gran mayoría de colecciones de la vida real. Cuando la colección que queremos ordenar es aleatoria. En ese caso, Bucket Sort tarda O (n) en terminar, lo que lo hace muy eficiente.

Conclusión

Para resumir todo, comenzamos obteniendo una introducción a lo que es la ordenación de Bucket y continuamos discutiendo lo que necesitamos saber antes de saltar a su implementación en Python. Después de la implementación, hemos realizado un análisis de complejidad rápido.