Question

Bucket sort is an algorithm that falls into the category of "specialized" sorts that have certain advantages but rely on properties of the array that may not be suitable for all situations. The algorithm itself is simple and uses an array of counters. Given an array of size n, the pseudocode is:

Initialize an array of integers of size range(n), bucketCount[], all set to 0

For i in each array element 0 ... n

increase bucketCount[array[i]] by 1

range(n) is the numeric range of the input (for example: if the numbers fall into the range 0-49, you would need an array of 50 counters).

After completing the above loop, you can use another loop to rearrange values into sorted order using the counters in bucketCount[].

Assignment

1. Add an implementation of bucketSort() to your template from Lab 5. You can leave the existing sort() function in the code (and use a new name for this one) or replace the existing sort() function.
2. Verify that the array is sorted in ascending order using the same way as before (verifying a[i + 1] >= a[i] for all i).
3. You can assume that your input falls into a certain range (i.e. restrict them during the add() operation). This would also determine the size of your counters array.
4. After verifying that your code is correct, consider these questions,
   • What do you think is the "big O" complexity of this algorithm?
   • What is the main limitation of this method of sorting? Why doesn't it work for everything?
   • Leave your answers in the comments along with your code.

Answer 1

Bucket sort with the help of counters:

Lets assume you have a array [0, 9, 8, 4, 3]. It has n = 5 elements in range 0-10.

So we will create a bucketCount array with size 11 as 10 is our range.

bucketCount[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

Now count the occurences of each array element and store them in bucketCount.

Now bucketCount will look like this:

bucketCount = {1, 0, 0, 3, 1, 0, 0, 0, 1, 1}

Now calculate prefix sum + arr[i] or each element in bucketCount. Prefix sum of index is the sum of all elements from index 0 to i - 1.

After that bucketCount will be like this

bucketCount = {1, 1, 1, 4, 5, 5, ,5, 5, 6, 7}

Now make a sorted_order array of size n to store the sorted array.

we will calculate it using prefix sum, as the prefix sum of index i in bucketCount shows its position in the sorted array. we will do like this:

sorted_order[bucketCount[a[i]] - 1 ] = a[i];

now decrement the index value for other values identical to a[i]
bucketCount[a[i]]--;

Now we have our sorted_array as : {0, 3, 4, 8, 9}

We will copy this array back to arr[]. We got our sorted array.....

C++ program:

#include<bits/stdc++.h>
using namespace std;

//defining range for our input
#define RANGE 50

void bucketSort(int a[], int n){

    //creating bucketCount array of size equal to range of input
    int bucketCount[RANGE + 1];

    //initilaize bucletCount with 0
    for(int i = 0; i <= RANGE; i++)
        bucketCount[i] = 0;

    //counting occurrence of each element and storing it in bucketCount
    for(int i = 0; i < n; i++){
        bucketCount[a[i]]++;
    }

    //Now calculate the prefix sum of array bucketCount
    //prefix sum for index i is just the sum of all elements from 0 to i
    //By doing this we are calculating the position of each element in sorted array
    for(int i = 1; i <= RANGE; i++)
        bucketCount[i] += bucketCount[i - 1];

    //now create a new array to store the sorted order of elements
    int sorted_order[n];

    //now place the elements to their respective indexes in ascending order
    for(int i = 0; i < n; i++){

        //placing a[i] at correct index in sorted_order
        sorted_order[bucketCount[a[i]] - 1 ] = a[i];

        //now decrement the index value for other values identical to a[i]
        bucketCount[a[i]]--;
    }

    //replacing elements of a[] by elements of sorted_order[]

    for(int i = 0; i < n; i++)
        a[i] = sorted_order[i];

}

int main(){
    int n;
    cout<<"Enter the number of elemenst you want to enter: ";
    cin>>n;

    int arr[n];
    cout<<"Enter "<<n<<" elements within 0 - "<<RANGE<<" range"<<endl;
    //Read n array elements
    for(int i = 0; i < n; i++)
        cin>>arr[i];

    //calling our bucketSort function to sort elements in ascending order
    bucketSort(arr, n);

    //displaying the osrted array elements
    cout<<"Your array is sorted now:\n";
    for(int i = 0; i < n ; i++)
        cout<<arr[i]<<" ";

    return 0;
}

Output:

if it helps you, do upvote as it motivates us a lot!