How can I bucket sort an array of integers that contains negative numbers?
And, what's the difference between bucket sort and counting sort?
How can I bucket sort an array of integers that contains negative numbers?
And, what's the difference between bucket sort and counting sort?
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}
#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++
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;
}
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;
}