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

place rest of code ? this part only finds max digit from all numbers — james
– james, Commented Feb 9, 2012 at 23:51

Matteo Italia · Accepted Answer · 2012-02-09 23:59:34Z

2

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.

edited Feb 9, 2012 at 23:59

answered Feb 9, 2012 at 23:53

Matteo Italia

128k18 gold badges219 silver badges313 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Richard Over a year ago

How do I find the maximum int like you say to optimize the code? Thanks

Matteo Italia Over a year ago

Do the same thing but with the number instead of the logarithm, i.e. iterate on the array and at each iteration check if the absolute value of the current element is larger than the "current maximum", if it is store it (the absolute value) as the new maximum. At the end of the cycle, take its base-10 logarithm, round it as in your code and you'll get the maximum number of digits needed.

noMAD · Accepted Answer · 2012-02-09 23:51:55Z

0

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.

answered Feb 9, 2012 at 23:51

noMAD

7,85420 gold badges62 silver badges97 bronze badges

Comments

daerty0153 · Accepted Answer · 2012-02-09 23:56:17Z

0

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

answered Feb 9, 2012 at 23:56

daerty0153

5241 gold badge6 silver badges11 bronze badges

Comments

David Nehme · Accepted Answer · 2012-02-09 23:59:45Z

0

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

edited Feb 9, 2012 at 23:59

answered Feb 9, 2012 at 23:51

David Nehme

21.7k8 gold badges82 silver badges123 bronze badges

Comments

james · Accepted Answer · 2012-02-10 00:03:57Z

0

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)

answered Feb 10, 2012 at 0:03

james

1,7531 gold badge16 silver badges26 bronze badges

Collectives™ on Stack Overflow

C++ Radix sort algorithm

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related