C Exercises: Sort numbers using Bucket Sort method

C Programming Searching and Sorting Algorithm: Exercise-25 with Solution

Write a C program that sorts numbers using the Bucket sort method.

From Wikipedia,
Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm.

Bucket sort works as follows:
Set up an array of initially empty "buckets".
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.

Pseudocode:

function bucketSort(array, k) is
    buckets ← new array of k empty lists
    M ← the maximum key value in the array
    for i = 1 to length(array) do
        insert array[i] into buckets[floor(k × array[i] / M)]
    for i = 1 to k do
        nextSort(buckets[i])
    return the concatenation of buckets[1], ...., buckets[k]

Sample Solution:

Sample C Code:

// Source: https://bit.ly/2TPGpVK
#include <assert.h>
# include <stdio.h>
#include <stdlib.h>
#define NARRAY 8    /* array size */
#define NBUCKET 5   /* bucket size */
#define INTERVAL 10 /* bucket range */

struct Node
{
    int data;
    struct Node *next;
};

// Function prototypes
void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);

// Function to perform Bucket Sort on an array
void BucketSort(int arr[])
{
    int i, j;
    struct Node **buckets;

    // Allocate memory for an array of pointers to the buckets
    buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);

    // Initialize pointers to the buckets
    for (i = 0; i < NBUCKET; ++i)
    {
        buckets[i] = NULL;
    }

    // Put items into the buckets
    for (i = 0; i < NARRAY; ++i)
    {
        struct Node *current;
        int pos = getBucketIndex(arr[i]);
        // Create a new node for the current element and insert it into the corresponding bucket
        current = (struct Node *)malloc(sizeof(struct Node));
        current->data = arr[i];
        current->next = buckets[pos];
        buckets[pos] = current;
    }

    // Check the contents of each bucket
    for (i = 0; i < NBUCKET; i++)
    {
        printf("Bucket[\"%d\"] : ", i);
        printBuckets(buckets[i]);
        printf("\n");
    }

    // Sort each bucket using Insertion Sort
    for (i = 0; i < NBUCKET; ++i)
    {
        buckets[i] = InsertionSort(buckets[i]);
    }

    // Check the contents of each bucket after sorting
    printf("--------------\n");
    printf("Buckets after sorted\n");
    for (i = 0; i < NBUCKET; i++)
    {
        printf("Bucket[\"%d\"] : ", i);
        printBuckets(buckets[i]);
        printf("\n");
    }

    // Put items back to the original array
    for (j = 0, i = 0; i < NBUCKET; ++i)
    {
        struct Node *node;
        node = buckets[i];
        // Traverse the nodes in the bucket and put them back to the original array
        while (node)
        {
            // Precondition for avoiding out-of-bounds access
            assert(j < NARRAY);
            arr[j++] = node->data;
            node = node->next;
        }
    }

    // Free memory
    for (i = 0; i < NBUCKET; ++i)
    {
        struct Node *node;
        node = buckets[i];
        // Traverse the nodes in the bucket and free memory
        while (node)
        {
            struct Node *tmp;
            tmp = node;
            node = node->next;
            free(tmp);
        }
    }
    free(buckets);
    return;
}

// Function to perform Insertion Sort on a linked list
struct Node *InsertionSort(struct Node *list)
{
    struct Node *k, *nodeList;

    // Need at least two items to sort
    if (list == NULL || list->next == NULL)
    {
        return list;
    }

    nodeList = list;
    k = list->next;
    nodeList->next = NULL; /* 1st node is the new list */

    // Iterate through the linked list and perform insertion sort
    while (k != NULL)
    {
        struct Node *ptr;

        /* check if insert before the first node */
        if (nodeList->data > k->data)
        {
            struct Node *tmp;
            tmp = k;
            k = k->next;  // important for the while loop
            tmp->next = nodeList;
            nodeList = tmp;
            continue;
        }

        // Find the position to insert the current node
        for (ptr = nodeList; ptr->next != NULL; ptr = ptr->next)
        {
            if (ptr->next->data > k->data)
                break;
        }

        // If a position is found, insert the current node
        if (ptr->next != NULL)
        {
            struct Node *tmp;
            tmp = k;
            k = k->next;  // important for the while loop
            tmp->next = ptr->next;
            ptr->next = tmp;
            continue;
        }
        else
        {
            // If no position found, append the current node to the end of the sorted list
            ptr->next = k;
            k = k->next;  // important for the while loop
            ptr->next->next = NULL;
            continue;
        }
    }
    return nodeList;
}

// Function to get the bucket index for a given value
int getBucketIndex(int value)
{
    return value / INTERVAL;
}

// Function to print the elements of an array
void print(int ar[])
{
    int i;
    for (i = 0; i < NARRAY; ++i)
    {
        printf("%d ", ar[i]);
    }
    printf("\n");
}

// Function to print the elements of a linked list (bucket)
void printBuckets(struct Node *list)
{
    struct Node *cur = list;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
}

// Main function
int main(void)
{
    int array[NARRAY] = {19, 15, 0, -3, 23, 7, 11, 23};

    printf("Original array\n");
    print(array);
    printf("------------\n");

    // Call the BucketSort function to sort the array
    BucketSort(array);

    printf("------------\n");
    printf("Sorted array\n");
    print(array);

    return 0;
}

Sample Output:

Original array
19 15 0 -3 23 7 11 23
------------
Bucket["0"] : 7 -3 0
Bucket["1"] : 11 15 19
Bucket["2"] : 23 23
Bucket["3"] :
Bucket["4"] :
--------------
Buckets after sorted
Bucket["0"] : -3 0 7
Bucket["1"] : 11 15 19
Bucket["2"] : 23 23
Bucket["3"] :
Bucket["4"] :
------------
Sorted array
-3 0 7 11 15 19 23 23

--------------------------------
Process exited after 0.571 seconds with return value 0
Press any key to continue . . .

Flowchart:

C Programming Code Editor:

Previous: Write a C program that sort numbers using Comb sort method.
Next:Write a C program that sort numbers using Binary insertion sort method