//Example: Radix Sort an array of arbitrary integer, ranged 0 to 29, of size 32. 
#define SIZE 32
#define RANGE 2 //at most to tens digit

struct Cell
{
  char* data; 
  int occur;
};

void radixSort(struct Cell* space)
{
  /*
    int i;
    for(i = RANGE - 1; i >= 0; i--)    
      stableSort(space, i);
  */

  space = stableSort(space, 1, 9);
  space = stableSort(space, 0, 9);
    

  return;
}

struct Cell* stableSort(struct Cell* space, int dig, int range) //Counting Sort
{
  int i, j, rem, temp;

  //Counting array
  int* C = (int*) malloc ((range+1) * sizeof(int));

  //Output array
  struct Cell* B = (struct Cell*) malloc (SIZE * sizeof(struct Cell));
  for(i = 0; i < SIZE; i++)
    {
      B[i].data = (char*) malloc(RANGE * sizeof(char));
      B[i].occur = 0;
    }
  


  //Initialize Counting array, C
  for(i = 0; i <= range; i++)
    C[i] = 0;
  
  //C[i] contains how many occurence of element i in array A.
  /*
   * A = {1, 2, 5, 1, 2}
   * C = {2, 2, 0, 0, 1}, array A has two elements of value 1, two elements of value 2, and so on. 
   */
  for(i = 0; i < SIZE; i++)
    {
      rem = atoi(space[i].data) % (int)pow(10, RANGE - dig) / (int)pow(10, RANGE - dig - 1);     
      C[rem] = C[rem] + 1;
    }
    
    
  //Now, C[i] contains the number of elements less or equal to i
  /*
   *C = {2, 4, 4, 4, 5}
   */
  for(i = 1; i <= range; i++)
    C[i] = C[i] + C[i-1];


  //Dispatch to output array 
  for(i = SIZE - 1; i >= 0; i--)
    {
      rem = atoi(space[i].data) % (int)pow(10, RANGE - dig) / (int)pow(10, RANGE - dig - 1);

      strcpy(B[C[rem]-1].data, space[i].data);
      B[C[rem]-1].occur = space[i].occur;

      C[rem] = C[rem] - 1;
    }

  free(space);
  free(C);

  return B;
}