C++ Radix sort algorithm

Question

Trying to understand radix sort for my data structures class. My teacher showed us a sample of radix sort in C++. I don't understand what the for loop for the digits does, she said something about maximum digits. Also when I try this in VS it says log10 is an ambiguous call to an overloaded function.

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

Can anyone explain what this for loop does and why i get that ambiguous call error? Thanks

Answer 1

That piece of code is just a search for the number of digits needed for the "longest" integer; that's probably needed to allocate some buffer later.

log10 gives you the power of ten that corresponds to its argument, which, rounded to the next integer (hence the +1 followed by the (int) cast, which results in truncation), gives you the number of digits required for the number.

The argument of log10 is a bit of a mess, since abs is called twice when just once would suffice. Still, the idea is to pass to log10 the absolute value of the number being examined if it's not zero, or 1 if it is zero - this because, if the argument were zero, the logarithm would diverge to minus infinity (which is not desirable in this case, I think that the conversion to int would lead to strange results).

The rest of the loop is just the search for the maximum: at each iteration it calculates the digits needed for the current int being examined, checks if it's bigger than the "current maximum" (d) and, if it is, it replaces the "current maximum".

The d+=1 may be for cautionary purposes (?) or for the null-terminator of the string being allocated, it depends on how d is used afterward.

As for the "ambiguous call" error: you get it because you are calling log10 with an int argument, which can be converted equally to float, double and long double (all types for which log10 is overloaded), so the overload to choose is not clear to the compiler. Just stick a (double) cast before the whole log10 argument.

---

By the way, that code could have been simplified/optimized by just looking for the maximum int (in absolute value) and then taking the base-10 logarithm to discover the number of digits needed.

Answer 2

Log base 10 + 1 gives you the total number of digits present in a number. Essentially here, you are checking every element in the array A[] and if the element is == 0 you store 1 in the digits_temp variable. You initialize d = 1 as a number should have atleast 1 digit, and if it has more than 1 you replace it with the number of digits calculated.

Hope that helps.

Answer 3

There are 3 types of definition for log10 function which are float,double,long double input.

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

So you need to static cast it as double to avoid the error.

(int)log10(x)+1 gives the number of digit present in that number.

Rest is simple implementation of Radix Sort

Answer 4

You see the warning because log10 is defined for float, double and long double but not integer and it's being called with a integer. The compiler can convert the int into any of those types so the call is ambiguous.

The for loop is doing a linear search for the maximum of digits in any of the numbers in the array. It is unnecessarily complicated and slow because you can simply searched for the largest absolute value in A then taken the log10 of that.

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

Answer 5

Rest of code is missing so cant exactly determined usage.

But basically Radix sort goes over all INTEGERS and sort them comparing Digit Digit starting from least significant upwards.

the first part of code only determines the max digit count+1 from integers in array, this could be used to normalize all numbers to same length for easy handling.

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