bucket sort

Bucket Sort in C

Bucket sort is a comparison sort algorithm that operates 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. Here are the steps for implementing bucket sort in C:

  1. Create Buckets: Create an array of buckets to hold the elements. The number of buckets can vary based on the input data and the specific implementation.

  2. Distribute Elements: Iterate through the input array and distribute the elements into their respective buckets based on some criteria. This can be done using a hashing function or another method to determine which elements go into which buckets.

  3. Sort Each Bucket: Sort each bucket individually. This can be done using another sorting algorithm, such as insertion sort, quicksort, or mergesort.

  4. Concatenate Buckets: Concatenate the sorted buckets to obtain the sorted array of elements.

Below is a simple example of bucket sort in C:

#include <stdio.h>

// A utility function to print an array
void printArray(float arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%f ", arr[i]);
    }
    printf("\n");
}

// A function to sort the input array using bucket sort
void bucketSort(float arr[], int n) {
    // Create buckets
    int i, j;
    int count[n];
    for (i = 0; i < n; i++) {
        count[i] = 0;
    }

    // Distribute elements to the buckets
    for (i = 0; i < n; i++) {
        (count[(int)(n * arr[i])])++;
    }

    // Sort each bucket and concatenate
    for (i = 0, j = 0; i < n; i++) {
        for (; count[i] > 0; (count[i])--) {
            arr[j++] = ((float)i) / n;
        }
    }
}

// Driver program to test above function
int main() {
    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Unsorted array: \n");
    printArray(arr, n);

    bucketSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

This example demonstrates a simple implementation of bucket sort in C. The input array is first distributed into buckets, then each bucket is sorted individually, and finally, the sorted buckets are concatenated to obtain the sorted array.

[[SOURCE 1]]