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 鈥嬧媏n 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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *