2012-02-09 18 views
1

Попытка понять сортировку radix для моего класса структур данных. Мой учитель показал нам образец рода radix в C++. Я не понимаю, что делает цикл for для цифр, она сказала что-то о максимальных цифрах. Также, когда я пытаюсь это сделать в VS, он говорит, что log10 является двусмысленным вызовом перегруженной функции.C++ Radix sort algorithm

void RadixSort(int A[], int size) 
{ 
    int d = 1; 
     for(int i = 0; i < size; ++i) 
     { 
      int digits_temp; 
      digits_temp=(int)log10(abs(A[i]!=0 ? abs(A[i]) : 1)) +1; 
      if(digits_temp > d) 
       d = digits_temp; 
     } 
     d += 1; 

*rest of the implementation* 
} 

Может ли кто-нибудь объяснить, что это за цикл, и почему я получаю эту неоднозначную ошибку вызова? Спасибо

+0

место остального кода? эта часть только находит максимальную цифру из всех номеров. – james

ответ

2

Этот фрагмент кода представляет собой просто поиск количества цифр, необходимых для «самого длинного» целого числа; это, вероятно, необходимо для выделения некоторого буфера позже.

log10 дает силу десять, что соответствует его аргументу, который, округленному до следующего целого числа (отсюда +1 с последующим (int) гипсом, что приводит к усечению), дает количество цифр, необходимые для числа ,

Аргумент log10 - это немного беспорядок, поскольку abs вызывается дважды, когда только один раз будет достаточно. Тем не менее, идея состоит в том, чтобы перейти к log10 абсолютное значение проверяемого числа, если оно не равно нулю, или 1, если оно равно нулю, - потому что, если аргумент был равен нулю, логарифм расходится до минус бесконечности (что нежелательно в этом случае я думаю, что преобразование в int приведет к странным результатам).

Остальная часть цикла - это просто поиск максимума: на каждой итерации он вычисляет цифры, необходимые для текущего текущего объекта, проверяет, больше ли он «текущего максимума» (d), и если это , он заменяет «текущий максимум».

d+=1 может быть предостерегающим (?) Или для нуль-терминатора выделенной строки, это зависит от того, как используется d.

Что касается «неоднозначного вызова» ошибка: вы получите это, потому что вы звоните log10 с int аргументом, который может быть преобразован в равной степени float, double и long double (все типы, для которых log10 перегружен), поэтому перегрузка выбирать не понятно компилятору. Просто приклейте бросок (double) перед целым аргументом log10.


Кстати, этот код может быть упрощен/оптимизировано путем просто ищем максимальный int (по абсолютной величине) и затем принимая по основанию 10 логарифма, чтобы обнаружить количество цифр, необходимых.

+0

Как найти максимальный int, как вы говорите, чтобы оптимизировать код? Спасибо – Richard

+0

Выполняйте то же самое, но с номером вместо логарифма, т. Е. Итерации по массиву, и при каждой итерации проверяйте, больше ли абсолютное значение текущего элемента, чем «текущий максимум», если оно хранится (абсолютное значение) в качестве нового максимума. В конце цикла возьмите свой логарифм base-10, округлите его, как в вашем коде, и вы получите максимальное количество цифр. –

+0

Получил, спасибо большое! – Richard

0

Вы видите предупреждение, потому что log10 определен для float, double и long double, но не целого, и он вызывается с целым числом. Компилятор может преобразовать int в любой из этих типов, чтобы вызов был неоднозначным.

Цикл for выполняет линейный поиск максимального количества цифр в любом из чисел в массиве. Это излишне сложно и медленно, потому что вы можете просто найти наибольшее абсолютное значение в A, а затем взять log10.

void RadixSort(int A[], int size) 
{ 
    int max_abs = 1; 
    for(int i = 0; i < size; ++i) 
    { 
     if(abs(A[i] > max_abs) 
      max_abs = abs(A[i]); 
    } 
    int d += log10(float(max_abs)); 

    /* rest of the implementation */ 
} 
0

Базовая база 10 + 1 дает общее количество цифр в количестве. По существу здесь вы проверяете каждый элемент в массиве A[], и если элемент == 0, вы сохраняете 1 в переменной digits_temp. Вы инициализируете d = 1, так как число должно иметь как минимум 1 цифру, а если оно больше 1, вы заменяете его на количество вычисленных цифр.

Надеюсь, что помогает.

0

Существует 3 типа определения для функции log10, которые являются float, double, long double input.

log10(static_cast<double> (abs(A[i]!=0 ? abs(A[i]) : 1))); 

Таким образом, вам необходимо, чтобы статические данные были выбраны как двойные, чтобы избежать ошибки.

(int) log10 (x) +1 дает количество цифр, присутствующих в этом номере.

Отдых простая реализация Radix Sort

0

Остальной код отсутствует, так косяк точно определяется использование.

Но в основном сортировка Radix охватывает все INTEGERS и сортирует их, сравнивая цифровую цифру, начиная с наименее значимого вверх.

первая часть кода определяет максимальное количество цифр + 1 из целых чисел в массиве, это может быть использовано для нормализации всех чисел до такой же длины для удобства обработки.

i.e (1,239,2134) - (0001,0239,2134)