C Exercises: Sort numbers using Bucket Sort method
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
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics