Thursday, 6 March 2014

Program of RadixSort

void radixSort(vector<int>& a, int base)
{
  int const MAX = 10;
  static vector<int> buckets[MAX];
  int pow = 1;
 
  for (int i = 0; i < MAX; ++i)
  {
    buckets[i].resize(a.size());
    buckets[i][0] = 0;
  }

  for (int i = 0; i < base; ++i, pow *= 10)
  {
    for (int j = 0; j < MAX; ++j)
    {
      buckets[j][0] = 0;
    }

    for (int j = 0; j < a.size(); ++j)
    {
      int index = (a[j] / pow) % 10;
      buckets[index][++buckets[index][0]] = a[j];
    }
     
    int cnt = 0;
    for (int j = 0; j < MAX; ++j)
    {
      for (int k = 0; k < buckets[j][0]; ++k)
      {
        a[cnt++] = buckets[j][k + 1];
      }
    }
  }
}

void RadixSort(int A[], int size)
{
    int d = 1;
        for(int i = 0; i < size; ++i)
        {
            int digits_temp;
            digits_temp=(int)log10(abs(A[i]!=0 ? abs(A[i]) : 1)) +1;
            if(digits_temp > d)
                d = digits_temp;
        }
        d += 1;

*rest of the implementation*
{

No comments:

Post a Comment