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\$
3
  • \$\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\$ Jun 3, 2017 at 14:14
  • \$\begingroup\$ @BenSteffan except that std::sort is in C++, and the question is tagged c ;-) \$\endgroup\$
    – janos
    Jun 3, 2017 at 15:18
  • \$\begingroup\$ @janos Oh my, what a blunder. Note to self: Next time, read question tags properly. \$\endgroup\$ Jun 3, 2017 at 15:21

1 Answer 1

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\$
5
  • \$\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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