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

#define RADIX 10

void RadixSort(int *list, int list_length, int num_digits);
int *auxList, *list;

int main()
{
    int i;

    list = (int *) malloc(5 * sizeof(int));
    auxList = (int *) malloc(5 * sizeof(int));
    list[0] = 7;
    list[1] = 19;
    list[2] = 3;
    list[3] = 196;
    list[4] = 79;
    RadixSort(list, 5, 3);
    for (i = 0; i < 5; i++) {
	printf("%d\n", list[i]);
    }
    free(list);
    free(auxList);

    return 0;
}

void RadixSort(int *list, int list_length, int num_digits)
{
    int bin[RADIX];
    int column = 1, i, j;

    for (j = 0; j < num_digits; j++) {
	
        /* set up bins, count elements with
	 * each sort of digit
	 */
	for (i = 0; i < RADIX; i++) {
	    bin[i] = 0;
	}
	for (i = 0; i < list_length; i++) {
	    int dig = list[i] / column % RADIX;
	    bin[dig]++;
	}

	/* work out the starting index
	 * for each bin
	 */
	bin[RADIX-1] = list_length - bin[RADIX-1];
	for (i = RADIX - 2; i > -1; i--) {
	    bin[i] = bin[i+1] - bin[i];
	}
    
	/* hash each element by the current digit */
	for (i = 0; i < list_length; i++) {
	    int dig = list[i] / column % RADIX;
	    auxList[bin[dig]] = list[i];
	    bin[dig]++;
	}

	/* copy elements from auxList to list */
	for (i = 0; i < list_length; i++) {
	    list[i] = auxList[i];
	}

	column *= RADIX;
    }

}