# How to sort array by divisor sum faster?

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

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

## 1 Answer

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.

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