How to sort array by divisor sum faster?

Question

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

• Ben Steffan: 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.
• janos: @BenSteffan except that std::sort is in C++, and the question is tagged c ;-)
• Ben Steffan: @janos Oh my, what a blunder. Note to self: Next time, read question tags properly.

Answer 1

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.

• Timʘtei: 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
• janos: @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.
• Timʘtei: You are right. I do not know why I was thinking that INT_MAX is about 2.000.000. Thanks!
• janos: @Timʘtei maybe because it's about 2.000.000.000, a couple of zeros difference ;-)
• Martin R: 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>.