c - 基数排序循环错误

Question

我正试图在 C 中实现整数的基数排序，但我遇到了一个我似乎无法修复的循环错误。这是代码和输出。我不知道错误的确切部分，所以请原谅帖子的长度。

有人可以指出我的错误吗？

#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;
}    

输出:

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

代码中有两个问题:

1. 你的交换码:temp = src_ptr; src_ptr = dest_ptr; dest_ptr = src_ptr; 应该引用 temp 两次(我的编译器告诉我你做错了，因为它说“error: variable 'temp' set but not used [-Werror =unused-but-set-variable]").您需要让您的编译器生成类似的警告，然后注意它们。交换代码应该是:temp = src_ptr; src_ptr = dest_ptr; dest_ptr = temp; 当然可以。这是必要的改变；这还不够。

   我希望我的代码能够在以下情况下干净地编译:

   gcc -g -O3 -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition -Wold-style-declaration -Werror  radixsort.c -o radixsort
   

2. 当你换类时，你没有正确使用j。你有:

   cnt[(src_ptr[i] >> i*GROUP) & mask]++;
   dest_ptr[map[(src_ptr[i] >> i*GROUP) & mask]++] = src_ptr[i];
   

   你需要:

   cnt[(src_ptr[i] >> j*GROUP) & mask]++;
   dest_ptr[map[(src_ptr[i] >> j*GROUP) & mask]++] = src_ptr[i];
   

此代码似乎排序正确:

#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;
}

示例输出:

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

通用代码

上面的代码将 GROUP 用于两个不同的目的。一个是要排序(和打印)的列表的长度。一个是用于进行基数排序的数字组的数量。下面的代码被概括为将列表大小与基数组分开。它还清理了一些原始代码中未修复的注释等。

#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;
}

这段代码现在假定整数值都在 0x0000..0xFFFF 范围内(4 个 nybbles，每个 4 位，或 16 位数字)。

示例输出:

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