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?

Re: Having trouble understanding radix sorts 80 80

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 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.