C++: Counting Sort

[sunburnt]

Any optimizations?


// v is the vector to sort
// min is the smallest item in the array
// max is the largest.
// counting sort functions in O(range * n) time
void counting_sort(vector<int>& v, int min, int max)
{
int range = max - min + 1;
int* counts = new int[range];
int offset = -min;
vector<int>::size_type size = v.size();

memset(counts, 0, range * sizeof(int));

for(int i = 0; i < size; ++i)
++counts[v[i] + offset];

int index = 0;
for(int i = 0; i < range; ++i)
while(counts[i]--)
v[index++] = i - offset;

delete [] counts;

return;
}

[wossname]

Yeah. Not sure if it makes the code any faster, but it does drop 1 line..

// v is the vector to sort
// min is the smallest item in the array
// max is the largest.
// counting sort functions in O(range * n) time
void counting_sort(vector<int>& v, int min, int max)
{
int range = max - min + 1;
int *counts = new int[range];
int offset = -min;
vector<int>::size_type size = v.size();

memset(counts, 0, range * sizeof(int));

for(int i = 0; i < size; ++i)
++counts[v[i] + offset];

//int index = 0;
for(int i = 0, index = 0; i < range; ++i)
while(counts[i]--)
v[index++] = i - offset;

delete [] counts;

return;
}

[CornedBee]

Doesn't make it faster.

What's the algorithm to do, exactly? What do you want to count?

[sunburnt]

I use counting sort when I need to sort a large amount of numbers that fall in a relatively small range. Because counting sort never has to compare numbers, it can operate in O(n) time, but is only useful in a narrow range of situations.

What it actually does is instead of comparing, it counts (hence, counting sort ;))the number of time each value occurs and places that value in an array at the index of the value. When it finishes counting, it then iterates over the array and places each item back in the original array the number of times indicated.

[CornedBee]

Radix or Bucket sort, this kind of thing?