0

Hey guys,

I'm trying to understand how radix sort works in C++ : I've looked over the C++ implementation from wikipedia:

void radixsort(int *a, int n)
{
  int i, b[MAX], m = a[0], exp = 1;
  for (i = 0; i < n; i++)
  {
    if (a[i] > m)
      m = a[i];
  }

  while (m / exp > 0)
  {
    int bucket[10] =
    {  0 };
    for (i = 0; i < n; i++)
      bucket[a[i] / exp % 10]++;

      //accumulate
    for (i = 1; i < 10; i++)
      bucket[i] += bucket[i - 1];

      //transfer
    for (i = n - 1; i >= 0; i--)
      b[--bucket[a[i] / exp % 10]] = a[i];

    for (i = 0; i < n; i++)
      a[i] = b[i];
    exp *= 10;

    #ifdef SHOWPASS
      printf("\nPASS   : ");
      print(a, n);
    #endif
  }
}

The portion I'm having trouble with is the accumulation and transfer parts (commented above). What's the point in the accumulation step, and how does the transfer portion work? Can someone shed some light?

Edited by Duki

2
Contributors
1
Reply
6
Views
4 Years
Discussion Span
Last Post by deceptikon
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.