2
\$\begingroup\$

I am sorting an array by divisor sum in ascending order. If two or more numbers have the same sum of divisors they have to be sorted in ascending order. The problem I have is that my version is not fast enough. Here is my code:

int divisorSum( double number )
{
    double sum = number + 1;
    for( int i = 2; i <= number / 2; i++ )
        if(( int )number % i == 0 )
            sum += i;
    return sum;
}
void sortByDivisorSum( double *array, int length )
{
    for( int i = 0; i < length; i++ )
    {
        for( int j = i + 1; j < length; j++ )
        {
            if(( divisorSum( array[ i ]) > divisorSum( array[ j ])) || (( divisorSum( array[ i ] ) == divisorSum( array[ j ])) && ( array[ i ] > array[ j ])))
            {
                array[ i ] += array[ j ];
                array[ j ] = array[ i ] - array[ j ];
                array[ i ] -= array[ j ];
            }
        }
    }
}
void readArrayy(double *array, int length)
{
    for(int index = 0; index < length; index++)
        scanf("%lf", &array[index]);
}
int main( void )
{
    int length, in;
    scanf( "%d", &length );
    double ar[ length ];
    readArrayy( ar, length );
    sortByDivisorSum( ar, length );
    for( in = 0; in < length; in++ )
    {
        printf( "%.0lf ", ar[in]);
    }
    return 0;
}

How to solve this in a faster way?

Input:

10
24 46 11 36 48 35 27 28 49 6

Output:

6 11 27 35 28 49 24 46 36 48
\$\endgroup\$
  • \$\begingroup\$ Use a fast sorting algorithm, something along the lines of quicksort. If you do not want to implement this yourself, use std::sort, which will be reasonably fast. \$\endgroup\$ – Ben Steffan Jun 3 '17 at 14:14
  • \$\begingroup\$ @BenSteffan except that std::sort is in C++, and the question is tagged c ;-) \$\endgroup\$ – janos Jun 3 '17 at 15:18
  • \$\begingroup\$ @janos Oh my, what a blunder. Note to self: Next time, read question tags properly. \$\endgroup\$ – Ben Steffan Jun 3 '17 at 15:21
2
\$\begingroup\$

Many elements of this code can be much faster.

Calculating the sum of divisors will be faster if you:

  • Iterate until sqrt(number) instead of number / 2, and include divisor pairs (i and number / i)
  • Change the type of number from double to int

(See also my review of your related question.)

Use a faster sorting algorithm, for example quicksort or merge sort. And when you, avoid mistakes like if(( divisorSum( array[ i ]) > divisorSum( array[ j ])) || (( divisorSum( array[ i ] ) == divisorSum( array[ j ])) && ( array[ i ] > array[ j ]))), which recomputes the sum of divisors twice for array[i] and array[j]. You could store the results of expensive operations in a variable, and then you can use that variable multiple times in conditions.

\$\endgroup\$
  • \$\begingroup\$ I agree with storing expensive operations in variables and to iterate to sqrt( number ), but: I can't change double to int because array elements value is in range 0-100.000.000 \$\endgroup\$ – Timʘtei Jun 3 '17 at 15:48
  • 1
    \$\begingroup\$ @Timʘtei you haven't mention that constraint in the question. But I don't see how it matters. According to limits.h, INT_MAX is easily high enough for your needs. \$\endgroup\$ – janos Jun 3 '17 at 15:51
  • \$\begingroup\$ You are right. I do not know why I was thinking that INT_MAX is about 2.000.000. Thanks! \$\endgroup\$ – Timʘtei Jun 3 '17 at 15:55
  • 1
    \$\begingroup\$ @Timʘtei maybe because it's about 2.000.000.000, a couple of zeros difference ;-) \$\endgroup\$ – janos Jun 3 '17 at 15:57
  • \$\begingroup\$ Strictly speaking, INT_MAX=2,147,483,647 is a "typical" value and the C standard only requires that is at least 32,767 (but 16-bit integers probably are used only on embedded systems or other special platforms). An alternative is use types like int32_tfrom <stdint.h>. \$\endgroup\$ – Martin R Jun 3 '17 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.