¿Qué es el algoritmo de BucketSort?

También conocido como ordenamiento por casilleros , por botes o  bin sort es algoritmo de ordenamiento que ordena los elementos de una lisita dividiéndolos en botes dependiendo de su rango  y luego ordena cada bote individualmente, esto ultimo  lo hace  utilizando otro algoritmo de ordenamiento, como InsertionSort o MergeSort, o recursivamente utilizando el propio BucketSort.

Eficiencia.

La eficacia del algoritmo de ordenamiento por botes está influenciada por diversos factores, como la cantidad de botes, la disposición de los elementos y el método de ordenamiento empleado para clasificar los botes individualmente. En términos generales, su complejidad temporal promedio es de O(n + k), donde "n" es la cantidad de elementos y "k" representa la cantidad de botes. No obstante, esta eficiencia puede fluctuar según la implementación específica y las particularidades de los datos. El ordenamiento por botes resulta particularmente beneficioso cuando los elementos están uniformemente distribuidos y sus valores son conocidos.

Pasos del Algoritmo. 

El proceso de Bucket Sort generalmente sigue estos pasos:

1. Distribución en botes: Los elementos del arreglo se distribuyen en un número finito de botes, basados en ciertos criterios, como el valor de los elementos. Esto se puede hacer dividiendo el rango de valores en el que se encuentran los elementos y asignando cada elemento a su bote correspondiente.

2. Ordenamiento de los botes: Cada bote se ordena individualmente. Esto se puede hacer utilizando cualquier algoritmo de ordenamiento, dependiendo de las características de los elementos en el bote. Por ejemplo, si el rango de valores es pequeño, se puede utilizar Insertion Sort para ordenar cada bote.

3. Combinación de los botes: Finalmente, los elementos de los botes se combinan para producir el arreglo ordenado. Esto se logra visitando cada bote en orden y colocando sus elementos en el arreglo final.

Implementación en Python.

Imagine que desea ordenar la siguiente lista: 

   [ 29, 25, 3, 49, 9, 37, 21, 43 ]

El procedimiento seria el siguiente: 

                                            Imagen de Booyabazooka.

El código en Python seria el siguiente:

def bucket_sort(arr):

    # Normalizar los elementos en el rango [0, 1]
    max_val = max(arr)
    arr_normalized = [num / max_val for num in arr]


    # Crear una lista de "botes" vacíos
    n = len(arr)
    buckets = [[] for _ in range(n)]

    # Distribuir los elementos en los botes
    for num in arr_normalized:
        index = int(num * (n - 1))  # Calcular el índice del bote para el elemento
        buckets[index].append(num)   # Agregar el elemento al bote correspondiente

    # Ordenar cada bote individualmente (usando Insertion Sort en este caso)
    for bucket in buckets:
        insertion_sort(bucket)

    # Concatenar los botes ordenados para obtener el arreglo ordenado final
    result = []

    for bucket in buckets:
        result.extend(bucket)

    # Desnormalizar los elementos en el rango original
    result = [int(num * max_val) for num in result]
    return result



def insertion_sort(arr):
    # Implementación simple de Insertion Sort
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


# Ejemplo de uso
arr =  [29, 25, 3, 49, 9, 37, 21, 43]
sorted_arr = bucket_sort(arr)
print("Arreglo ordenado:", sorted_arr)

Resultado:

     Arreglo ordenado: [3, 9, 21, 25, 29, 37, 43, 49]     

Ventajas y Desventajas. 

Ventajas:

1. Eficiencia en distribuciones uniformes: Cuando los elementos están uniformemente distribuidos entre los botes, Bucket Sort puede ser muy eficiente, ya que distribuye los elementos de manera equitativa y luego los ordena de manera individual, lo que puede resultar en un buen rendimiento.

2. Eficiente en datos con rangos conocidos: Si los datos tienen un rango conocido y los botes se pueden asignar de manera adecuada a este rango, Bucket Sort puede ser muy eficiente, ya que puede optimizarse para trabajar con estos datos específicos.

3. Adaptable a otros algoritmos de ordenamiento: Bucket Sort puede utilizar otros algoritmos de ordenamiento como Insertion Sort, Merge Sort o Quick Sort para ordenar los botes individualmente, lo que permite adaptarse a diferentes distribuciones de datos y optimizar el rendimiento.

Desventajas:

1. Ineficiencia en distribuciones no uniformes: Si los elementos no están distribuidos uniformemente entre los botes, la eficiencia de Bucket Sort puede verse comprometida, ya que algunos botes pueden contener muchos más elementos que otros, lo que aumenta el tiempo de ejecución.

2. Uso de memoria: Bucket Sort puede requerir una cantidad significativa de memoria adicional para almacenar los botes, especialmente si el rango de valores es grande y se necesitan muchos botes. Esto puede ser una limitación en sistemas con recursos limitados.

3. Complejidad del algoritmo de ordenamiento interno: La eficiencia de Bucket Sort puede depender en gran medida del algoritmo de ordenamiento utilizado para ordenar los botes individualmente. Algunos algoritmos de ordenamiento pueden ser más eficientes que otros dependiendo de las características de los datos.