sorting - Algorithms for bucket sort

Question

How can I bucket sort an array of integers that contains negative numbers?
And, what's the difference between bucket sort and counting sort?

Answer 1

Bucket sort for negative values

Using Bucket sort for negative values simply requires mapping each element to a bucket proportional to its a distance from the minimal value to be sorted.

For example when using a bucket per value (as suggested above) for the following input would be as follows:

input array: {4, 2, -2, 2, 4, -1, 0}
min = -2
bucket0: {-2}
bucket1: {-1}
bucket2: {0}
bucket3: {}
bucket4: {2, 2}
bucket5: {}
bucket6: {4, 4}

Suggested algorithm

#A: array to be sorted
#count: number of items in A
#max: maximal value in A
#min: minimal value in A
procedure BucketSort(A, count, max, min)
    #calculate the range of item in each bucket
    bucketRange = (max - min + 1) / bucketsCount
    #distribute the item to the buckets
    for each item in A:
        bucket[(item.value - min) / bucketRange].push(item)
    #sort each bucket and build the sorted array A
    index = 0
    for bucket in {0...bucketsCount}:
        sort(bucket)
        for item in {0...itemsInBucket}:
            A[index] = item
            index++

C++ implementation

Notice the bucketRange which is proportional to the range between max and min

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>    // std::sort
#include <stdlib.h>     // rand
#include <limits>       // numeric_limits

using namespace std;

#define MAX_BUCKETS_COUNT (10) // choose this according to your space limitations

void BucketSort(int * arr, int count, int max, int min)
{
    if (count == 0 or max == min)
    {
        return;
    }

    // set the number of buckets to use
    int bucketsCount = std::min(count, MAX_BUCKETS_COUNT);
    vector<int> *buckets = new vector<int>[bucketsCount];

    // using this range we will we distribute the items into the buckets
    double bucketRange = (((double)max - min + 1) / (bucketsCount));

    for (int i = 0; i < count; ++i)
    {
        int bucket = (int)((arr[i] - min)  / bucketRange);
        buckets[bucket].push_back(arr[i]);
    }

    int index = 0;
    for (int i = 0; i < bucketsCount; ++i)
    {
        // here we sort each bucket O(klog(k) - k being the number of item in the bucket
        sort(buckets[i].begin(), buckets[i].end());
        for (vector<int>::iterator iter = buckets[i].begin(); iter != buckets[i].end(); ++iter)
        {
            arr[index] = *iter;
            ++index;
        }
    }

    delete[] buckets;

}

Testing the code

int main ()
{
    int items = 50;
    int data[items];

    int shift = 15;//inorder to get some negative values in the array
    int max = std::numeric_limits<int>::min();
    int min = std::numeric_limits<int>::max();
    printf("before sorting: ");
    for (int i = 0; i < items; ++i)
    {
        data[i] = rand() % items - shift;
        data[i] < min ? min = data[i]: true;
        data[i] > max ? max = data[i]: true;
        printf("%d ,", data[i]);
    }
    printf("
");

    BucketSort(data, items, max, min);

    printf("after sorting: ");
    for (int i = 0; i < items; ++i)
    {
        printf("%d ,", data[i]);
    }
    printf("
");

    return 0;
}