Radix sort (C)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C | Java

An implementation of radix sort for unsigned int in c. It uses counting sort for each iteration (see Category:Counting sort for more implementations of counting sort).



[edit] radix_sort_uint()

This function takes the pointer to, and size, of an array, and the number of bits used as the key in each iteration.

void radix_sort_uint(unsigned int *a, size_t size, int bits)
	unsigned int mask;
	unsigned int rshift=0u;
	unsigned int *p, *b, *b_orig;
	unsigned int i;
	unsigned int key;
	int cntsize;
	int *cntarray;

[edit] Memory

We use an array of the same size as the original array to store the result of each iteration.

	b=b_orig=malloc(size*sizeof(unsigned int));

An array is needed to store the count for each key value.

	cntarray=calloc(cntsize, sizeof(int));


[edit] The main algorithm

mask is the bitmask used to extract the sort key. We start with the bits least significant bits and left-shift it the same amount at each iteration. When all the bits are shifted out of the word, we are done.


	for(mask=~(UINT_MAX<<bits); mask; mask<<=bits, rshift+=bits) {

[edit] Counting sort

We count each key value.

		for(p=a; p<a+size; ++p) {
			key=(*p & mask)>>rshift;

Here, we sum up how many elements there are with lower key values, for each key.


		for(i=1; i<cntsize; ++i) cntarray[i]+=cntarray[i-1];

The values in cntarray are used as indexes for storing the values in b. b will then be completely sorted on this iteration's key. Elements with the same key value are stored in their original internal order.


		for(p=a+size-1; p>=a; --p) {
			key=(*p & mask)>>rshift;

[edit] Cleanup

We swap the a and b pointers, so that the next iteration works on the current b, which is now partially sorted.


		p=b; b=a; a=p;

cntarray is cleaned up for the next iteration.


		bzero(cntarray, cntsize * sizeof(int));

If the completely sorted array is in the malloc'ed array, we must copy it to the array provided by the user.


	if(a==b_orig) memcpy(b, a, size*sizeof(unsigned int));


[edit] Test driver

This test program uses 4 bits for the key. radix_sort_uint() will accept any number of bits for the key, but it will allocate at least 2bits ints of storage.


int main()
	int i;
	unsigned int a[]={

	printf("Before radix sort:\n");
	for(i=0; i<sizeof a/sizeof(unsigned int); ++i) 
		printf(" %d", a[i]);

	radix_sort_uint(a, sizeof a/sizeof(int), 4);

	printf("After radix sort:\n");
	for(i=0; i<sizeof a/sizeof(unsigned int); ++i) 
		printf(" %d", a[i]);

	return 0;
Download code