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 3 Years Ago by Duki

This article has been dead for over six months. Start a new discussion instead.