Radix Сортировка с использованием C ++

Question

Предположим, у меня есть куча чисел. Я должен сначала поместить наименее значащую цифру в соответствующее ведро. Пример: 530, я должен сначала положить в ведро 0. Для номера 61 я должен положить в ведро 1.

Я планировал использовать многомерный массив для этого. Поэтому я создаю 2-мерный массив, который nrows равен 10 (для 0 ~ 9), а ncolumns 999999 (потому что я не знаю, насколько большим будет список):

    int nrows = 10;
    int ncolumns = 999999;

    int **array_for_bucket = (int **)malloc(nrows * sizeof(int *));
         for(i = 0; i < nrows; i++)
             array_for_bucket[i] = (int *)malloc(ncolumns * sizeof(int));

    left = (a->value)%10;
    array_for_bucket[left][?? ] = a->value;

Тогда я создал один узел с именем a. В этом узле a есть значение 50. Чтобы выяснить, в какое ведро я хочу его поместить, я вычисляю «left», и я получил 0. Поэтому я хочу поместить это a-> значение в ведро 0. Но теперь я я застрял Как мне положить это значение в ведро? Я должен использовать массив указателей, чтобы сделать это.

Я долго думал, но все еще не мог найти хороший способ сделать это. Поэтому, пожалуйста, поделитесь некоторыми идеями со мной. спасибо!

Answer 1

Существует гораздо более простой способ сделать это, и вместо radix*nkeys места вам нужен только буфер размером nkeys.

Выделите второй буфер, который может соответствовать клавишам nkeys. Теперь сделайте первый проход по вашим данным и просто посчитайте, сколько ключей окажется в каждом сегменте. Теперь вы можете создать массив указателей размером radix, где каждый указатель находится в начале этого блока в выходном буфере. Наконец, второй проход, хотя данные перемещают ключи. Каждый раз, когда вы перемещаете клавишу, увеличивайте указатель сегмента.

Вот код на C, который нужно преобразовать в C ++:

void radix_sort(int *keys, int nkeys)
{
    int *shadow = malloc(nkeys * sizeof(*keys));

    int bucket_count[10];
    int *bucket_ptrs[10];
    int i;

    for (i = 0; i < 10; i++)
        bucket_count[i] = 0;

    for (i = 0; i < nkeys; i++)
        bucket_count[keys[i] % 10]++;

    bucket_ptrs[0] = shadow;
    for (i = 1; i < 10; i++)
        bucket_ptrs[i] = bucket_ptrs[i-1] + bucket_count[i-1];

    for (i = 0; i < nkeys; i++)
        *(bucket_ptrs[keys[i] % 10]++) = keys[i];

    //shadow now has the sorted keys

    free(shadow);
}

Но я, возможно, неправильно понял вопрос. Если вы делаете что-то немного отличное от radix, пожалуйста, добавьте некоторые детали.

Answer 2

Это C ++, мы больше не используем malloc.Мы используем контейнеры.Двумерный массив - это вектор векторов.

vector<vector<int> > bucket(10);
left = (a->value)%10;
bucket[left].push_back(a->value);

Answer 3

C ++ - не моя сильная сторона, но этот код из wikipedia-Raidx Sort очень исчерпывающий и, вероятно, больше в C ++, чем то, что вы реализовали до сих пор.Надеюсь, это поможет

Answer 4

Посмотрите Boost Контейнеры указателей Библиотека, если вы хотите хранить указатели.