Radix Sort with C++

Question

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

Я планировал использовать многомерный массив для этого. Таким образом, я создаю 2-dimenional массив, 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

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

Answer 3

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

Answer 4

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

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