1

I have understood that the compare function is sorting the values so that it shows a combination of numbers in decreasing order.

For example: Given [3, 30, 34, 5, 9], the largest formed number is 9534330.

 int compare(const void *a1,const void *b1){
        int a = *(int*)a1;
        int b = *(int*)b1;
        int i=0;
        char arr[10000]={0};
        char brr[10000]={0};
        sprintf(arr, "%d%d", a, b);
        sprintf(brr, "%d%d", b, a);
        int k = strlen(arr);
        for(i=0; i < k; i++){
            if(arr[i] != brr[i])
                return brr[i] - arr[i];
        }
        return b-a;
    }
    char* largestNumber(const int* A, int n1) {
        char *ans = (char*) calloc(10000000,sizeof(char));
        int i=0, count=0;
         qsort(A, n1, sizeof(int), compare);
        if(A[0] == 0){  
            ans[0] = '0'; ans[1]=0; return ans;
        }
        for(i=0; i<n1; i++){
            int k = A[i];
            // printf("%d ", k);
            count += sprintf(ans+count, "%d", k);
        }
        // printf("\n");
        ans[count] = 0;
        return ans;
    }

My doubts are as follows:

  1. How does this piece of code work?

    for(i=0; i < k; i++){
    if(arr[i] != brr[i])
        return brr[i] - arr[i];
}

    It is comparing the contents of arr and brr, but how is it returning the value so that the values are getting sorted in this fashion?

  2. And even if it returns the values, they should be printed in increasing order. Why is it showing them in decreasing order?

Fabio says Reinstate Monica
  • 5,271
  • 9
  • 40
  • 61
Abhijit Sarkar
  • 71
  • 6
  • 1
    Notes: 1) Could use `int k = sprintf(arr, "%d%d", a, b);` "sprintf function returns the number of characters written in the array, not counting the terminating null character, or a negative value if an encoding error occurred." 2) `char arr[10000]={0};` is fairly extreme, maybe `char arr[100]={0};`? 3) the whole `for(i=0; i < k; i++){ if(arr[i] != brr[i]) ...` looks akin to `strcmp()`. – chux - Reinstate Monica Mar 08 '17 at 20:16
  • If you are using `sprintf` and loops within the `compare` function provided to `qsort`, it could take forever and a day. That function is intended to make a simple comparison of values, or several if there is a hierarchy in a `struct`. But your `compare` function seems to be trying to take over the job of `qsort`. Perhaps you should re-think the algorithm. The solution might benefit from a recursive approach. – Weather Vane Mar 08 '17 at 20:21
  • @WeatherVane Disagree - it is still pretty much an n log n problem., `sprintf()` is simply forming the lexicographical values in which to compare. – chux - Reinstate Monica Mar 08 '17 at 20:24
  • @chux, perhaps, I added another sentence while you were posting. – Weather Vane Mar 08 '17 at 20:25
  • It seems a bit excessive to allocate a ten-million-character space in which to record the answer, though I guess that depends to some extent on how large `n1` may be, and on the bounds on elements of the input array. – John Bollinger Mar 08 '17 at 21:19
  • [don't cast the result of `malloc` family in C](http://stackoverflow.com/q/605845/995714) – phuclv Mar 11 '17 at 06:18
  • compare() should compare its two arguments which, in this case, appear to be `int` a & b. Simple tests like `if (a < b) ...` (or even `return a-b`) should be used. Comparing instead their ascii representation is wrong. – linuxfan says Reinstate Monica Mar 11 '17 at 06:30

1 Answers1

0

This compare function is quite odd.
To understand how it works, let's start considering what qsort expects: it expects a function that accepts 2 numbers, a and b, and which

returns an integer less than, equal to, or greater than 0, if the first argument is considered respectively less than, equal to, or greater than the second.

In this case, as we will see, it actually returns the opposite result, that is, it returns an integer less than, equal to, or greater than 0, if the second argument is considered respectively less than, equal to, or greater than the first. This is just because the author of this code wants to sort in descending order and not in ascending order.

That said, this compare function is a special one: let's see what it does. Although it works with numbers (it accepts void*, which is a generic pointer, but then it casts both parameters to int* and dereferences them), it doesn't compare them numerically, and not even in the classic alphanumeric way. Rather, it indicates in which order the two numbers, once converted to string, have to be concatenated to generate the sequence of digits that, interpreted as a number, yields the largest possible result (this is hinted at by the name of the other function, largestNumber). It does so by indicating as largest number the one that must be taken first. It sounds complicated, but some examples will clarify.

Let's take the numbers 3 and 4. If you treat them as strings ("3" and "4") you can concatenate them in two different orders, getting either "34" or "43". Now, convert these strings back to numbers: which one is larger? Clearly, 34 < 43, and if you want the largest number (43) you must take 4 as first number, and 3 as second. In this case the function will tell you that the largest number is 4. It does so by returning a positive number (1, in this case).

Let's take 30 and 4 instead. If you concatenate them you get either "304" or "430". Since 304 < 430, the function tells you that the largest number is 4. So, from this point of view, 4 > 30, which is the opposite of the numeric sort.

If you take 3 and 30, the two possible concatenations are "330" and "303", and since 330 > 303 you have to take 3 first, and the function tells you that 3 > 30. Again, it's the opposite of the numeric sort.

If you take 30 and 30 you have to choose between "3030" and "3030", which are identical, and in this case the function returns 0.

Now a tricky case: if you compare 3 and 33, the two "stringified" numbers are identical ("333" and "333"), so we'd expect 0. Actually in this case the function tells you that the largest number is the second one... But it doesn't matter, as the result would be identical.

And how does the comparison work, exactly? First, the numbers are converted to string using sprintf. Consider that the 2 strings (let's call them "ab" and "ba") must have the same length, so it checks the length of one with strlen, and then the loop checks every digit, starting from the first. If the digit is the same between ab and ba, it does nothing and just goes to the next one; if it is different, it compares them and returns the digit of brr minus the digit of arr. For example, when comparing 3 and 30, arr would contain 330 and brr 303. At the first iteration (when i==0) it would check the first digit: it's 3 for both, so you can't choose which number is higher yet. Move to the second digit: 3 > 0, so arr > brr, so the function must return a negative number, and indeed it does: it returns 0 - 3 = -3.

So, the function compares a and b and returns:

  • a negative number if they yield the largest number by concatenating them in this order (a, b);
  • 0, if the numbers are the same, so that it doesn't matter in which order they are taken;
  • a positive number if they have to be concatenated in the opposite order (b, a) to yield the largest number.

This table shows the result of the classic numeric sort, the classic alphanumeric sort, and this custom sort (which I've called "largest stringified number sort")

 a   b    Numeric sort   Alphanumeric sort   Largest stringified number sort
 3   4      3 <   4          3 <   4            34 <    43  --> return  1 >  0 -->  3  <  4
30   4     30 >   4         30 <   4           304 <   430  --> return  1 >  0 -->  30 <  4
 3  30      3 <  30          3 <  30           330 >   303  --> return -3 <  0 -->  3  > 30
 3  31      3 <  31          3 <  31           331 >   313  --> return -2 <  0 -->  3  > 31
 3  32      3 <  32          3 <  32           332 >   323  --> return -1 <  0 -->  3  > 32
 3  33      3 <  33          3 <  33           333 ==  333  --> return 30 >  0 -->  3  < 33
 3  34      3 <  34          3 <  34           334 <   343  --> return  1 >  0 -->  3  < 34
30  30     30 == 30         30 == 30          3030 == 3030  --> return  0 == 0 --> 30 == 30

As to why they are printed in decreasing order, it's simply because of this line:

return brr[i] - arr[i];

If you want to see them in increasing order, change it to:

return arr[i] - brr[i];
Fabio says Reinstate Monica
  • 5,271
  • 9
  • 40
  • 61