Clasificación de cubeta en Python

En este tutorial, nos sumergiremos en la teoría y la implementación de Bucket Sort en Python. También exploraremos su complejidad temporal.

Introducción

En este tutorial, nos sumergiremos 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 Cubetas o Contenedores. Luego, el contenido de estos cubos se ordena, normalmente con otro algoritmo. Después de la clasificación, se agregan los contenidos de los cubos, formando una colección ordenada.

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

Implementaremos Bucket Sort en Python y analizaremos su complejidad temporal.

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

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

  1. Configure una lista de baldes vacíos. Se inicializa un depósito para cada elemento de la matriz.
  2. Iterar a través de la lista de deseos e insertar 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 elementos 0..n en cada cubo. Esto se desarrollará en la presentación visual del algoritmo.
  3. Clasifique 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 Tipo de inserción funciona de maravilla para nosotros aquí.
  4. Visita los cubos en orden. Una vez que se ordenan los contenidos de cada cubo, cuando se concatenan, generará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:

visualización de clasificación de cubos

El elemento más grande es 1.2 y la longitud de la lista es 6. Usando estos dos, averiguaremos el “tamaño” óptimo de cada cubeta. Obtendremos este número dividiendo el elemento más grande con la longitud de la lista. En nuestro caso, es 1.2/6 que es 0.2.

Al dividir el valor del elemento con este tamaño, obtendremos un índice para el depósito respectivo de cada elemento.

Ahora, crearemos baldes vacíos. Tendremos la misma cantidad de cubetas que los elementos de nuestra lista:

bucket sort visualization

Insertaremos los elementos en sus respectivos cubos. Teniendo en cuenta el primer elemento - 1.2/0.2 = 6, el índice de su respectivo cubo 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 tamaño al dividir el elemento más grande por la longitud.

Colocaremos este elemento en el cubo con el índice de 5:

bucket sort visualization

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

visualización de clasificación de cubos

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

visualización de tipo de cubo

Ahora, ordenaremos el contenido de cada cubeta no vacía. Usaremos la ordenación por inserción ya que es insuperable con listas pequeñas como esta. Después de la ordenación por inserción, los cubos se ven así:

visualización de tipo de cubo

Ahora, es solo cuestión de recorrer los cubos no vacíos y concatenar los elementos en una lista. Están ordenados y listos para funcionar:

bucket sort visualization

Implementación de clasificación de cubos en Python

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

 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
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 parámetro tamaño. Luego, instanciamos una lista de cubos vacíos y elementos insertados en función de su valor y el “tamaño” de cada cubo.

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

1
2
3
4
5
6
7
8
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 clasificación de cubo en ella:

1
2
3
4
5
6
7
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á:

1
2
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 de tiempo de clasificación de depósito {#complejidad de tiempo de clasificación de depósito}

Complejidad en el peor de los casos {#complejidad en el peor de los casos}

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

Si todos los elementos caen en el mismo cubo, la complejidad depende exclusivamente del algoritmo que usamos para ordenar los contenidos del cubo en sí.

Dado que estamos utilizando 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 ordenación de cubos también es O(n^2^).

Complejidad en el mejor de los casos

El mejor de los casos sería tener todos los elementos ya ordenados. Además, los elementos están distribuidos uniformemente. Esto significa que cada cubeta tendría el mismo número de elementos.

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

Complejidad promedio de casos

El caso promedio ocurre en la gran mayoría de las colecciones de la vida real. Cuando la colección que queremos ordenar es aleatoria. En ese caso, Bucket Sort toma O(n) para terminar, haciéndolo muy eficiente.

Conclusión

Para resumir todo, comenzamos con una introducción a lo que es el tipo de cubo y luego discutimos 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.