Answer to Question #276190 in C for MRM

Question

Given an array array[], its starting position l and its ending position r. Sort the array using Bucket Sort algorithm.

Input: N = 10

array[] = {10 9 7 8 6 2 4 3 5 1}

Output: 1 2 3 4 5 6 7 8 9 10 

Answer 1

#include <stdio.h>


void PrintArray(int arr[], int n) {
    for (int i=0; i<n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}


void BucketSort(int array[], int l, int r) {
    int x_min, x_max;
    int* bucket[5];
    int size[5];
    double dx;


    if ( l+1 >= r ) {
        return;
    }
    if ( r-l == 2) {
        if (array[l] > array[l+1]) {
            int tmp = array[l];
            array[l] = array[l+1];
            array[l+1] = tmp;
        }
        return;
    }


    x_min = x_max = array[l];
    for (int i=l+1; i<r; i++) {
        if (array[i] < x_min) { 
            x_min =  array[i];
        }
        else if (array[i] > x_max) {
            x_max = array[i];
        }
    }
    for (int i=0; i<5; i++) {
        bucket[i] = (int *) malloc((r-l)*sizeof(int));
        size[i] = 0;
    }


    dx = (x_max - x_min) / 5.0;
    for (int i=l; i<r; i++) {
        int idx = (array[i] - x_min) / dx;
        if (idx ==  5) {
            idx = 4;
        }
        bucket[idx][size[idx]] =  array[i];
        size[idx]++;
    }
    for (int i=0; i<5; i++) {
        BucketSort(bucket[i], 0, size[i]);
    }
    int ind = 0;
    for (int i=0; i<5; i++) {
        for (int j=0; j<size[i]; j++) {
            array[ind] = bucket[i][j];
            ind++;
        }
        free(bucket[i]);
    }
}


int main() {
    int array[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int n = sizeof(array)/sizeof(array[0]);


    PrintArray(array, n);
    BucketSort(array, 0, n);
    PrintArray(array, n);


    return 0;
}