🚀 go-pugleaf

Hi,

I ran into the c-code of a countsort program. People say that this is
the quickest sorting method available. Most of the source i understand
but there are three for-loops in which i don't realy know what they
do....

Can anyone tell me, in one or two lines, what happens in these
loops.....i marked the beginning of the loops with /* ??? */

Please cc any reply to bob_ross@dds.nl

Thanks a million,
Robbert


/** THE SOURCE **/

#include <stdlib.h>
#include <stdio.h>

void countsort(int *a, int n, int k)
{
  int *b = (int*) malloc(sizeof(int) * n);
  int *c;
  int i;

  ++k;
  c = (int*) malloc(sizeof(int) * k);

  for (i = 0; i < k; i++)
    {
      c[i] = 0;
    }

  
  /* ???? */
  for (i = 0; i < n; i++)
    {
      ++c[a[i]];
    }


  /* ???? */
  for (i = 1; i < k; i++)
    {
      c[i] += c[i - 1];
    }


  /* ???? */
  for (i = n - 1; i >= 0; i--)
    {
      b[c[a[i]] - 1] = a[i];
      --c[a[i]];
    }

  for (i = 0; i < n; i++)
    {
      a[i] = b[i];
    }

  free(c);
  free(b);
}

int a[] = { 10, 8, 6, 4, 3, 8, 0 };

int main(int argc, char* argv[])
{
  int i;
  const int n = sizeof(a) / sizeof(a[0]);
  printf("%d\n", n);

  for (i = 0; i < n; i++)
    {
      printf("%d ", a[i]);
    }
  printf("\n");

  countsort(a, n, 12);

  for (i = 0; i < n; i++)
    {
      printf("%d ", a[i]);
    }
  printf("\n");

  return 0;
}