Descripción del Algoritmo

La ordenación por cubetas, también conocida como ordenación por casillas, es una técnica eficiente cuando se trata de ordenar un conjunto de elementos. Si se puede construir un conjunto de k valores mucho más pequeño para n elementos, entonces se puede emplear la ordenación por recuento. La ordenación por cubetas construye n cubetas para dividir el conjunto de entrada, lo que reduce el espacio adicional requerido. Si una función hash, hash(A), distribuye uniformemente n elementos en n cubetas, la ordenación por cubetas puede lograr una complejidad temporal de O(n) en el peor de los casos. Para utilizar la ordenación por cubetas, se deben cumplir dos condiciones:

Distribución Uniforme Los datos de entrada deben estar distribuidos uniformemente dentro de un rango determinado. Basándose en esta distribución, el algoritmo crea cubetas para dividir los datos de entrada equitativamente.

Función Hash Ordenada Las cubetas deben ser ordenadas. Es decir, si i < j, los elementos en la cubeta b_i deben ser lexicográficamente menores que los elementos en la cubeta b_j.

La ordenación por cubetas no es adecuada para ordenar cadenas aleatorias, pero puede utilizarse para ordenar números de punto flotante distribuidos uniformemente en el intervalo [0, 1).

Una vez que todos los elementos a ordenar se han colocado en las cubetas, la ordenación por cubetas aplica la ordenación por inserción a los valores dentro de cada cubeta, de izquierda a derecha. Finalmente, los elementos de cada cubeta se extraen en orden y se utilizan para reconstruir el arreglo original.

A continuación, se detalla el proceso de la ordenación por cubetas:

1. Determinar el Número y Tamaño de las Cubetas

• Obtener el Rango de Valores: Primero, determine el valor máximo y mínimo del arreglo a ordenar para establecer el rango de valores.
• Determinar el Número de Cubetas: Basándose en el rango de valores y el número deseado de cubetas (o una regla de mapeo), divida el rango en subintervalos, donde cada subintervalo corresponde a una cubeta. El número de cubetas puede ser una constante predefinida o determinarse dinámicamente según el tamaño y rango del arreglo.
• Determinar el Tamaño de las Cubetas: El tamaño de cada cubeta puede ser fijo o determinado por una división uniforme del rango de valores. El tamaño y el número de cubetas, en conjunto, influyen en la eficiencia y el resultado de la ordenación por cubetas.

2. Asignar Elementos a las Cubetas

• Función de Mapeo: Utilice una función de mapeo f para asignar cada elemento del arreglo a ordenar a su cubeta correspondiente. La elección de la función de mapeo es crucial para la eficiencia, ya que debe distribuir los elementos uniformemente entre las cubetas.
• Asignar Elementos: Recorra el arreglo a ordenar y, utilizando la función de mapeo, asigne cada elemento a su cubeta correspondiente. Se pueden utilizar estructuras de datos como arreglos, listas enlazadas o colas para almacenar las cubetas.

3. Ordenar los Elementos Dentro de Cada Cubeta

• Seleccionar un Algoritmo de Ordenación: Ordene los elementos dentro de cada cubeta no vacía. Se puede emplear cualquier algoritmo de ordenación efectivo, como la ordenación por inserción, rápida o de montículos. El algoritmo elegido debe basarse en el número de elementos en la cubeta y la eficiencia general de la ordenación por cubetas.
• Ordenar Elementos de la Cubeta: Aplique el algoritmo de ordenación seleccionado a los elementos de cada cubeta.

4. Combinar los Elementos de las Cubetas

• Combinar Cubetas en Orden: Combine secuencialmente los elementos de todas las cubetas no vacías para formar un arreglo ordenado. Este proceso puede realizarse iterando a través de las cubetas en orden o utilizando otros algoritmos de combinación eficientes.
• Obtener la Secuencia Ordenada: Una vez completada la combinación, el arreglo resultante es la secuencia ordenada.

5. Consideraciones Importantes

• Distribución de Elementos: La efectividad de la ordenación por cubetas depende de la distribución de los elementos en el arreglo a ordenar. Si los elementos están distribuidos de manera muy desigual, algunas cubetas pueden contener una gran cantidad de elementos, lo que reduce la eficiencia de la ordenación dentro de la cubeta. Por lo tanto, es importante considerar la distribución de los elementos al elegir la ordenación por cubetas.
• Función de Mapeo: La elección de la función de mapeo es fundamental para la eficiencia. Una buena función de mapeo debe distribuir los elementos de manera uniforme entre las cubetas, evitando así que algunas cubetas estén demasiado llenas o vacías.
• Algoritmo de Ordenación Dentro de la Cubeta: La selección del algoritmo de ordenación para las cubetas también afecta la eficiencia general. Al elegir este algoritmo, se debe considerar el número de elementos en la cubeta y la eficiencia total deseada.

Análisis de Complejidad

En la función sortPointers, cada elemento de entrada se inserta en su cubeta correspondiente utilizando la función hash proporcionada, lo que requiere un tiempo lineal O(n). Aunque los elementos dentro de las cubetas no están ordenados, debido a una función hash bien diseñada, sabemos que si i < j, todos los elementos en la cubeta b_i son menores que todos los elementos en la cubeta b_j.

Al extraer los valores de las cubetas y escribirlos de nuevo en el arreglo de entrada, se utiliza la ordenación por inserción cuando una cubeta contiene múltiples elementos. Para que la ordenación por cubetas exhiba un rendimiento O(n), el tiempo total dedicado a ordenar cada cubeta debe ser O(n). Definimos n_i como el número de elementos asignados a la cubeta b_i. Podemos considerar n_i como una variable aleatoria (utilizando teoría estadística). Ahora, consideremos el valor esperado de n_i, E[n_i]. La probabilidad de que cada elemento de entrada se inserte en una cubeta dada es 1/p, ya que cada valor se extrae uniformemente del intervalo [0, 1). Por lo tanto, E[n_i] = n * p = n * (1/n) = 1. La varianza es Var[n_i] = n * p * (1 - p) = (1 - 1/n). La varianza es importante porque algunas cubetas pueden estar vacías y otras pueden contener más de un elemento; debemos asegurarnos de que ninguna cubeta contenga demasiados elementos. Nuevamente, utilizando teoría estadística, obtenemos la siguiente igualdad: E[n_i^2] = Var[n_i] + E^2[n_i].

A partir de esta igualdad, podemos calcular el valor esperado de n_i^2. Este cálculo es crucial porque determina el costo de la ordenación por inserción, cuyo rendimiento en el peor de los casos es O(n^2). Calculamos E[n_i^2] = (1 - 1/n) + 1 = (2 - 1/n). Observamos que E[n_i^2] es una constante. Esto significa que cuando sumamos el costo total de ejecutar la ordenación por inserción en n cubetas, el rendimiento esperado total es O(n).

Casos de Aplicación

La ordenación por cubetas es el método de ordenación más rápido cuando los elementos a ordenar pueden ser distribuidos uniformemente mediante una función hash eficiente.

Si el espacio de almacenamiento no es una preocupación y los elementos obedecen a una relación de orden total, la ordenación por cubetas puede aprovechar esta información para ahorrar una cantidad significativa de esfuerzo.

Aquí hay varios escenarios de aplicación:

1. Distribución Uniforme de Datos Cuando los datos están distribuidos uniformemente en todo el rango de valores, la ordenación por cubetas asegura que cada cubeta contenga aproximadamente la misma cantidad de elementos. En esta situación, la ordenación por cubetas es muy eficiente porque la carga de ordenación de cada cubeta es relativamente equilibrada.
2. Grandes Volúmenes de Datos La ordenación por cubetas suele ser más eficiente que los algoritmos de ordenación por comparación simples (como la ordenación rápida o de fusión) al procesar grandes conjuntos de datos. Esto se debe a que la ordenación por cubetas evita un gran número de operaciones de comparación entre elementos, distribuyendo en su lugar los elementos en diferentes cubetas. Sin embargo, se debe tener en cuenta que la ordenación por cubetas requiere espacio de memoria adicional para almacenar las cubetas.
3. Rango de Datos Conocido Cuando se conoce el rango de valores de los datos, es más fácil determinar el número y el tamaño de las cubetas, lo que contribuye a la eficiencia y el rendimiento del algoritmo. Si el rango de valores es pequeño, se pueden usar cubetas de tamaño fijo; si el rango es grande, puede ser necesario ajustar dinámicamente el tamaño y el número de cubetas.
4. Selección Flexible de Algoritmo de Ordenación Dentro de la Cubeta La ordenación por cubetas permite utilizar diferentes algoritmos de ordenación dantro de cada cubeta. Esto permite seleccionar el algoritmo más adecuado según las características y la cantidad de datos dentro de la cubeta, optimizando así el rendimiento general.
5. Datos con Patrones o Periodicidad En algunos casos, los datos pueden exhibir ciertos patrones o periodicidad. La ordenación por cubetas puede aprovechar estos patrones para distribuir y ordenar los datos de manera más efectiva, mejorando la eficiencia de la ordenación.

Implementación del Algoritmo

#include <stdio.h>
#include <stdlib.h>

// Declaraciones de funciones externas (si fueran necesarias)
// extern int hash(void* elt);
// extern int numBuckets(int numElements);

// Ejemplo de implementación de hash y numBuckets para números uniformemente distribuidos en [0, 1)

// Número de cubetas
static int num_buckets_count = 0;

// El número de cubetas es igual al número de elementos
int get_num_buckets(int num_elements) {
    num_buckets_count = num_elements;
    return num_elements;
}

// Función hash para mapear elementos a cubetas.
// Como el rango de valores de la función hash es [0, 1), escalamos por el número de cubetas.
int map_to_bucket(double* value) {
    int bucket_index = num_buckets_count * (*value);
    // Asegurar que el índice esté dentro de los límites válidos
    if (bucket_index >= num_buckets_count) {
        bucket_index = num_buckets_count - 1;
    }
    return bucket_index;
}

// Estructura para los elementos dentro de una cubeta (lista enlazada)
typedef struct entry {
    void* element;
    struct entry* next;
} Entry;

// Estructura de una cubeta
typedef struct {
    int count;
    Entry* head;
} Bucket;

// Puntero a las cubetas
static Bucket* buckets_array = NULL;

// Función de comparación para ordenar enteros
int compare_integers(const void* a, const void* b) {
    int int_a = *((int*)a);
    int int_b = *((int*)b);
    return int_a - int_b;
}

// Extrae elementos de las cubetas y los coloca en el arreglo 'ar'
void extract_elements(Bucket* buckets, int (*comparison_func)(const void*, const void*), void** ar, int total_elements) {
    int current_index = 0;
    for (int i = 0; i < num_buckets_count; ++i) {
        Entry* current_entry = buckets[i].head;
        if (buckets[i].count == 0) {
            continue; // Saltar cubetas vacías
        }

        // Si solo hay un elemento, simplemente lo agregamos
        if (buckets[i].count == 1) {
            ar[current_index++] = current_entry->element;
            free(current_entry);
            buckets[i].head = NULL;
            buckets[i].count = 0;
            continue;
        }

        // Ordenar los elementos de la cubeta usando inserción y luego agregarlos al arreglo
        int bucket_start_index = current_index;
        ar[current_index++] = current_entry->element;
        Entry* temp_entry = current_entry;
        current_entry = current_entry->next;
        free(temp_entry);

        while (current_entry != NULL) {
            int j = current_index - 1;
            // Ordenación por inserción dentro del subarreglo
            while (j >= bucket_start_index && comparison_func(ar[j], current_entry->element) > 0) {
                ar[j + 1] = ar[j];
                j--;
            }
            ar[j + 1] = current_entry->element;
            temp_entry = current_entry;
            current_entry = current_entry->next;
            free(temp_entry);
            current_index++;
        }
        buckets[i].count = 0; // Marcar la cubeta como vacía después de la extracción
    }
}

// Función principal de ordenación por cubetas para punteros
void sort_pointers(void** ar, int n, int (*comparison_func)(const void*, const void*)) {
    num_buckets_count = get_num_buckets(n);
    buckets_array = (Bucket*)calloc(num_buckets_count, sizeof(Bucket));

    // Distribuir elementos en las cubetas
    for (int i = 0; i < n; ++i) {
        int bucket_idx = map_to_bucket(ar[i]);
        Entry* new_entry = (Entry*)calloc(1, sizeof(Entry));
        new_entry->element = ar[i];

        // Insertar al principio de la lista enlazada de la cubeta
        if (buckets_array[bucket_idx].head == NULL) {
            buckets_array[bucket_idx].head = new_entry;
        } else {
            new_entry->next = buckets_array[bucket_idx].head;
            buckets_array[bucket_idx].head = new_entry;
        }
        buckets_array[bucket_idx].count++;
    }

    // Extraer elementos ordenados de las cubetas
    extract_elements(buckets_array, comparison_func, ar, n);
    free(buckets_array); // Liberar la memoria asignada para las cubetas
}

int main() {
    int data[] = { 34, 7, 23, 32, 5, 62, 32, 15, 78, 9 };
    int n = sizeof(data) / sizeof(data[0]);

    // Crear un arreglo de punteros a enteros
    int** data_pointers = (int**)malloc(sizeof(int*) * n);
    if (data_pointers == NULL) {
        perror("Failed to allocate memory for pointers");
        return 1;
    }

    // Llenar el arreglo de punteros
    for (int i = 0; i < n; ++i) {
        data_pointers[i] = &data[i];
    }

    // Ordenar usando la ordenación por cubetas
    sort_pointers((void**)data_pointers, n, compare_integers);

    // Imprimir el arreglo ordenado
    printf("Arreglo ordenado:\n");
    for (int i = 0; i < n; ++i) {
        printf("%d ", *data_pointers[i]);
    }
    printf("\n");

    free(data_pointers); // Liberar la memoria asignada para los punteros
    return 0;
}

Queda la pregunta de cómo convertir este código C a C++ para que se ejecute correctamente en Visual Studio. Este código funciona en CLion pero no directamente en VS porque VS no admite el estándar C99 y C++ no permite la conversión implícita de tipos por defecto, lo que impide su ejecución directa.

Optimización del Algoritmo

En la ordenación hash, cada cubeta representa un valor único devuelto por la función hash. La ordenación hash no crea necesariamente n cubetas, sino que crea k cubetas. A medida que k aumenta, la ordenación hash se acelera. La clave de la ordenación hash reside en el valor entero devuelto por la función hash(e). Para cada elemento e, si a < b, entonces hash(a) <= hash(b). A continuación, se define una función hash hash(e) que calcula un valor basándose únicamente en las tres prmieras letras de un elemento (asumiendo que son minúsculas). Convierte los tres primeros caracteres en un valor utilizando una base de 26. Para la cadena "abcdefgh", sus tres primeros caracteres ("abc") se extraen y se convierten en 0 * 676 + 1 * 26 + 2 = 28. Esta cadena se insertaría en la cubeta etiquetada con el número 28.

// Número de cubetas a usar
int get_num_buckets(int num_elements) {
// Ejemplo: 26 * 26 * 26 cubetas para 3 letras minúsculas
return 26 * 26 * 26;
}

// Función hash para determinar a qué cubeta se debe mapear cada elemento.
// Calcula el valor basado en los tres primeros caracteres.
int hash_string_prefix(void* elt) {
char* str = (char*)elt;
// Convertir caracteres a índices (a=0, b=1, ...) y calcular el valor
return (((str[0] - 'a') * 676) + ((str[1] - 'a') * 26) + ((str[2] - 'a') * 1));
}

El rendimiento de la ordenación hash depende del tamaño de las cubetas y de la escala de entrada, como se ilustra en la siguiente tabla. Al comparar la ordenación hash con una ordenación rápida que utiliza el método de tres valores para seleccionar el pivote, y proporcionando un tiempo de ordenación comparable.

Tenga en cuenta que cuando hay 17576 cubetas y más de 8192 elementos (n > 8192), el rendimiento de la ordenación hash es superior al de la ordenación rápida, y esta tendencia continúa a medida que n aumenta. Sin embargo, con solo 676 cubetas y más de 32768 elementos (n > 32768, con un promedio de 48 elementos por cubeta), el costo de aplicar la ordenación por inserción a cada cubeta aumenta a medida que crece el conjunto de datos, lo que hace que la ordenación hash sea más lenta. De hecho, con 26 cubetas, cuando n > 256, el tiempo requerido para la ordenación hash se triplica cada vez que se duplica n. Cuando hay pocas cubetas, el rendimiento de la ordenación hash se aproxima a O(n^2).

Referencias

1. "Algorithm Design Manual"