CODEWITHSUNDEEP
c++sorting
user530664
user530664

Reputation:

Using Counting Sort on Negative values?

I have following code, but this works only for unsigned ints and my goal is to write a code which 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?

Upvotes: 7

Views: 4836

Answers (2)

user530664
user530664

Reputation:

thnks Anatolyg my new code is:

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]--; 
  }
}

Upvotes: 0

anatolyg
anatolyg

Reputation: 28269

Start by calculating 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] by a[i] - k_min; the rest should be easy.

Upvotes: 6

Related Questions