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

出力：

ソートされていない元のリスト: int: 26054 hex: 0x65c6 int: 3051 hex: 0xbeb int: 38586 hex: 0x96ba int: 39549 hex: 0x9a7d

ソートされたリスト: int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb

ソートされたバッファ: int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb int: 3051 hex: 0xbeb

score 2 · Accepted Answer

コードには 2 つの問題があります。

あなたのスワップコード:は 2 回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
```

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、2 つの異なる目的で使用しています。1 つは、リストの長さをソート (および印刷) するためのものです。1 つは、基数ソートを行う桁のグループの数です。以下のコードは、基数グループからリストサイズを分離するために一般化されています。また、元のコードなどで修正されていないいくつかのコメントをクリーンアップします。

#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 ビットの 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

c - 基数ソートのループのバグ

1 に答える 1

一般化されたコード

Related

Reference