C Online Compiler
Example: Bucket Sort Implementation in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS