Radix Sort Looping Bug

Question

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

Answer 1

There are two problems in the code:

1. 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
   

2. 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

Generalized Code

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