Example: Bucket Sort Implementation in C

// Bucket Sort Implementation
#include <stdio.h>
#include <stdlib.h> // Required for malloc, free

// Structure for a node in a linked list
struct Node {
    float data;
    struct Node* next;
};

// Function to create a new node for the linked list
struct Node* createNode(float data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        perror("Failed to allocate memory for node");
        exit(EXIT_FAILURE); // Exit if memory allocation fails
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node into a linked list in sorted order
// This effectively sorts elements within each bucket as they are added.
void insertSorted(struct Node** head, float data) {
    struct Node* newNode = createNode(data);
    struct Node* current;

    // If the list is empty or the new node should be the new head
    if (*head == NULL || (*head)->data >= newNode->data) {
        newNode->next = *head;
        *head = newNode;
    } else {
        // Traverse the list to find the correct position
        current = *head;
        while (current->next != NULL && current->next->data < newNode->data) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

// Function to free the memory allocated for a linked list
void freeList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

// Function to implement Bucket Sort
void bucketSort(float arr[], int n) {
    // Determine the number of buckets. For numbers between 0.0 and 1.0, 10 buckets
    // are a common choice, but can be adjusted based on data distribution.
    int numBuckets = 10;
    // Create an array of pointers to Node, which will act as the heads of our linked lists (buckets)
    struct Node* buckets[numBuckets];

    // Step 1: Initialize all buckets as empty
    for (int i = 0; i < numBuckets; i++) {
        buckets[i] = NULL;
    }

    // Step 2: Distribute array elements into different buckets
    for (int i = 0; i < n; i++) {
        // Calculate the bucket index for the current element.
        // Multiplies the number by `numBuckets` and takes the integer part.
        // E.g., 0.89 * 10 = 8.9, floor(8.9) = 8. So 0.89 goes into bucket 8.
        int bucketIndex = (int)(arr[i] * numBuckets);

        // Ensure the index does not exceed bounds for values very close to 1.0
        if (bucketIndex >= numBuckets) {
            bucketIndex = numBuckets - 1;
        }
        
        // Insert the element into the calculated bucket's linked list in sorted order
        insertSorted(&buckets[bucketIndex], arr[i]);
    }

    // Step 3: Sort individual buckets (implicitly done by insertSorted)
    // The `insertSorted` function ensures that elements are added to each bucket
    // in their correct sorted position, effectively sorting the individual buckets.
    // For very large buckets, other sorting algorithms like quicksort or mergesort
    // could be applied to the linked lists here if `insertSorted` isn't used.

    // Step 4: Concatenate all buckets back into the original array
    int index = 0; // Index for placing elements back into the original array
    for (int i = 0; i < numBuckets; i++) {
        struct Node* current = buckets[i];
        while (current != NULL) {
            arr[index++] = current->data; // Copy element back to array
            current = current->next;
        }
        // Free the memory allocated for the linked list in the current bucket
        freeList(buckets[i]);
    }
}

int main() {
    // Example array of floating-point numbers to be sorted
    float arr[] = {0.89, 0.45, 0.67, 0.23, 0.09, 0.99, 0.12, 0.78, 0.56, 0.34};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%.2f ", arr[i]);
    }
    printf("\n");

    // Call the bucketSort function
    bucketSort(arr, n);

    printf("Sorted array:   ");
    for (int i = 0; i < n; i++) {
        printf("%.2f ", arr[i]);
    }
    printf("\n");

    return 0;
}