C ++ Radix алгоритм сортировки

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

т.е. (1,239,2134) до (0001,0239,2134)

Answer 3

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

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

Поэтому вам нужно статически привести его к двойному типу, чтобы избежать ошибки.* (int) log10 (x) +1 дает количество цифр, присутствующих в этом числе.

Остальное - простая реализация Radix Sort

Answer 4

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

Answer 5

Вы видите предупреждение, потому что 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 */
}