Ошибка зацикливания сортировки по основанию

В коде две проблемы:

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 полубайта по 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