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?

This page goes into a little more detail for the same basic algorithm. It might help.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.