I'm attempting to implement a radix sort for integers in C and I am encountering a looping error that I cannot seem to fix. Here is the code and the output. I do not know the exact portion that is wrong so please excuse the post's length.
Can someone please point out my errors?
#include <stdio.h>
#define BINS 16
#define GROUP 4
int main(int argc, const char *argv[])
{
int mask = 0xf;
int i, j;
int list[] = {0x65c6, 0xbeb, 0x96ba, 0x9a7d};
int buffer[GROUP];
int *temp, *src_ptr, *dest_ptr;
int cnt[BINS];
int map[BINS];
map[0] = 0;
//init pointers to the list of unsorted numbers and temp buffer
src_ptr = list;
dest_ptr = buffer;
//print unsorted list
putchar('\n');
printf("unsorted list: \n");
for(i = 0; i < GROUP; i++)
printf("int: %d hex: 0x%x ", src_ptr[i], src_ptr[i]);
putchar('\n');
j = 0;
while(j < GROUP)
{
//initalize the count
for(i = 0; i < BINS; i++)
cnt[i] = 0;
//count significant digits. shifting i * group # of times
for(i = 0; i < GROUP; i++)
cnt[(src_ptr[i] >> i*GROUP) & mask]++;
//initalize the map
map[0] = 0;
for(i = 0; i < BINS; i++)
map[i] = 0;
//compute the map
for(i = 1; i < BINS; i++)
{
map[i] = (map[i - 1] + cnt[i - 1]);
}
//shift the elements in buffer[] and list[] via their pointers.
//shifting i * group # of times
for(i = 0; i < GROUP; i++)
{
dest_ptr[map[(src_ptr[i] >> i*GROUP) & mask]++] = src_ptr[i];
}
//perform a swap of list[] and buffer[] via their pointers
temp = src_ptr;
src_ptr = dest_ptr;
dest_ptr = src_ptr;
j++;
}
//print list for reference
putchar('\n');
printf("sorted list: \n");
for(i = 0; i < GROUP; i++)
printf("int: %d hex: 0x%x ", src_ptr[i], src_ptr[i]);
putchar('\n');
//print buffer for reference
putchar('\n');
printf("sorted buffer: \n");
for(i = 0; i < GROUP; i++)
printf("int: %d hex: 0x%x ", dest_ptr[i], dest_ptr[i]);
putchar('\n');
return 0;
}
output:
unsorted original list: int: 26054 hex: 0x65c6 int: 3051 hex: 0xbeb int: 38586 hex: 0x96ba int: 39549 hex: 0x9a7d
sorted list: int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb
sorted buffer: int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb
There are two problems in the code:
Your swap code: temp = src_ptr; src_ptr = dest_ptr; dest_ptr = src_ptr; should reference temp twice (and my compiler told me you were doing it wrong because it said "error: variable ‘temp’ set but not used [-Werror=unused-but-set-variable]"). You need to make your compiler generate similar warnings, and then heed them. The swap code should be: temp = src_ptr; src_ptr = dest_ptr; dest_ptr = temp; of course. That's a necessary change; it is not a sufficient change.
I expect my code to compile cleanly under:
gcc -g -O3 -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition -Wold-style-declaration -Werror radixsort.c -o radixsort
You've not made proper use of j when you're shifting. You have:
cnt[(src_ptr[i] >> i*GROUP) & mask]++;
dest_ptr[map[(src_ptr[i] >> i*GROUP) & mask]++] = src_ptr[i];
You need:
cnt[(src_ptr[i] >> j*GROUP) & mask]++;
dest_ptr[map[(src_ptr[i] >> j*GROUP) & mask]++] = src_ptr[i];
This code appears to sort correctly:
#include <stdio.h>
enum { BINS = 16 };
enum { GROUP = 4 };
enum { MASK = 0xF };
static void dump_array(char const *tag, size_t n, int a[n])
{
printf("%s:\n", tag);
for (size_t i = 0; i < n; i++)
printf("int: %5d hex: 0x%.4X\n", a[i], a[i]);
}
int main(void)
{
int i, j;
int list[] = {0x65C6, 0x0BEB, 0x96BA, 0x9A7D};
int buffer[GROUP];
int *temp, *src_ptr, *dest_ptr;
int cnt[BINS];
int map[BINS];
map[0] = 0;
// init pointers to the list of unsorted numbers and temp buffer
src_ptr = list;
dest_ptr = buffer;
// print unsorted list
dump_array("unsorted list", GROUP, src_ptr);
j = 0;
while (j < GROUP)
{
// initalize the count
for (i = 0; i < BINS; i++)
cnt[i] = 0;
// count significant digits. shifting i * group # of times
for (i = 0; i < GROUP; i++)
cnt[(src_ptr[i] >> j*GROUP) & MASK]++;
// initalize the map
map[0] = 0;
for (i = 0; i < BINS; i++)
map[i] = 0;
// compute the map
for (i = 1; i < BINS; i++)
{
map[i] = (map[i - 1] + cnt[i - 1]);
}
// shift the elements in buffer[] and list[] via their pointers.
// shifting i * group # of times
for (i = 0; i < GROUP; i++)
{
dest_ptr[map[(src_ptr[i] >> j*GROUP) & MASK]++] = src_ptr[i];
}
// perform a swap of list[] and buffer[] via their pointers
temp = src_ptr;
src_ptr = dest_ptr;
dest_ptr = temp;
j++;
}
// print list for reference
dump_array("sorted list", GROUP, src_ptr);
// print buffer for reference
dump_array("sorted buffer", GROUP, dest_ptr);
return 0;
}
Sample output:
unsorted list:
int: 26054 hex: 0x65C6
int: 3051 hex: 0x0BEB
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
sorted list:
int: 3051 hex: 0x0BEB
int: 26054 hex: 0x65C6
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
sorted buffer:
int: 26054 hex: 0x65C6
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
int: 3051 hex: 0x0BEB
The code above uses GROUP for two separate purposes. One is for the length of the list to be sorted (and printed). One is for the number of groups of digits to do the radix sort on. The code below is generalized to separate list size from radix groups. It also cleans up some comments not fixed in the original code, etc.
#include <stdio.h>
enum { BINS = 16 };
enum { GROUP = 4 };
enum { MASK = 0xF };
static void dump_array(char const *tag, size_t n, int a[n])
{
printf("%s:\n", tag);
for (size_t i = 0; i < n; i++)
printf("int: %5d hex: 0x%.4X\n", a[i], a[i]);
}
int main(void)
{
int list[] = {0x65C6, 0x0BEB, 0x96BA, 0x9A7D, 0x2917, 0x8A2C, 0xDEAD, 0xBEEF, 0xFACE };
enum { LIST_SIZE = sizeof(list) / sizeof(list[0]) };
int buffer[LIST_SIZE];
int cnt[BINS];
int map[BINS];
// init pointers to the list of unsorted numbers and temp buffer
int *src_ptr = list;
int *dst_ptr = buffer;
// print unsorted list
dump_array("unsorted list", LIST_SIZE, src_ptr);
for (int j = 0; j < GROUP; j++)
{
// initalize the count
for (int i = 0; i < BINS; i++)
cnt[i] = 0;
// count significant digits. shifting j * group # of times
for (int i = 0; i < LIST_SIZE; i++)
cnt[(src_ptr[i] >> j*GROUP) & MASK]++;
// initalize the map
for (int i = 0; i < BINS; i++)
map[i] = 0;
// compute the map
for (int i = 1; i < BINS; i++)
map[i] = (map[i - 1] + cnt[i - 1]);
// shift the elements in buffer[] and list[] via their pointers.
// shifting j * group # of times
for (int i = 0; i < LIST_SIZE; i++)
dst_ptr[map[(src_ptr[i] >> j*GROUP) & MASK]++] = src_ptr[i];
// perform a swap of list[] and buffer[] via their pointers
int *tmp_ptr = src_ptr;
src_ptr = dst_ptr;
dst_ptr = tmp_ptr;
}
// print list for reference
dump_array("sorted list", LIST_SIZE, src_ptr);
// print buffer for reference
dump_array("sorted buffer", LIST_SIZE, dst_ptr);
return 0;
}
This code now assumes that the integer values are all in the range 0x0000..0xFFFF (4 nybbles of 4 bits each, or 16-bit numbers).
Sample output:
unsorted list:
int: 26054 hex: 0x65C6
int: 3051 hex: 0x0BEB
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
int: 10519 hex: 0x2917
int: 35372 hex: 0x8A2C
int: 57005 hex: 0xDEAD
int: 48879 hex: 0xBEEF
int: 64206 hex: 0xFACE
sorted list:
int: 3051 hex: 0x0BEB
int: 10519 hex: 0x2917
int: 26054 hex: 0x65C6
int: 35372 hex: 0x8A2C
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
int: 48879 hex: 0xBEEF
int: 57005 hex: 0xDEAD
int: 64206 hex: 0xFACE
sorted buffer:
int: 26054 hex: 0x65C6
int: 38586 hex: 0x96BA
int: 10519 hex: 0x2917
int: 35372 hex: 0x8A2C
int: 39549 hex: 0x9A7D
int: 64206 hex: 0xFACE
int: 3051 hex: 0x0BEB
int: 57005 hex: 0xDEAD
int: 48879 hex: 0xBEEF