Using the negative count sorting function?

Question

I have the following code, but this only works for unsigned ints, and my goal is to write code that will work for all ints ...

void CountingSort(vector<int> & a, vector<int> & b) { int k=*max_element(a.begin(),a.end()); k++; vector <int> c(k); for (int i=0;i<a.size();i++) c[a[i]]++; for (int i=1;i<k;i++) c[i]=c[i]+c[i-1]; for (int i=0;i<a.size();i++) { b[c[a[i]]-1]=a[i]; c[a[i]]--; } } 

How can I change this to work for all integral types?

Answer 1

Start by calculating the minimum and maximum:

 int k_min=*max_element(a.begin(),a.end()); int k_max=*min_element(a.begin(),a.end()); int k = k_max - k_min + 1; 

Apply some changes to the following code, replacing a[i] with a[i] - k_min ; the rest should be easy.

Answer 2

thnks Anatolyg my new code:

 void Counting_Sort(vector <int>& a, vector <int>& b) { int k=*max_element(a.begin(), a.end()); int m=*min_element(a.begin(), a.end()); int n=k-m+1; vector<int>v(n); for(int i=0; i<a.size(); i++) v[a[i]-m]++; for(int i=1; i<v.size(); i++) v[i]=v[i]+v[i-1]; for(int i=a.size()-1;i>=0; i--) { b[v[a[i]-m]-1] = a[i]; v[a[i]-m]--; } }