C qsort strange behaviour

Question

I'm trying to do the following:

1. Allocate memory for array of dimension 7
2. Write the first 4 positions
3. Sort those 4 positions.
4. Write the remaining 3 positions
5. Sort the entire array.

I have the array (1,6,2,3), which after sorting becomes (1,2,3,6)

Then I write the remaining positions, which are (1,2,3,6,1,5,1)

After sorting it, I should be getting (1,1,1,2,3,5,6), but instead I'm getting (6,2,3,1,1,5,1).

Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int comp(const void* a, const void* b);

typedef struct{

    int peso;
 }aresta_;

int main(int argc, const char * argv[]) {

    aresta_* array /*struct array, has field peso of type int*/;
    int dim=7;
    int dim_aux=4;
    int i;

    array = (aresta_*) malloc(dim * sizeof(aresta_));

    array[0].peso=1;
    array[1].peso=6;
    array[2].peso=2;
    array[3].peso=3;


    printf("First sort:\n");
    for(i=0; i<dim_aux; i++)
        printf("%d ",array[i].peso);

    printf("\n");


    qsort(array, dim_aux, sizeof(array[0]), comp);


    for(i=0; i<dim_aux; i++)
        printf("%d ",array[i].peso);

    printf("\n\n");

    array[4].peso=1;
    array[5].peso=5;
    array[6].peso=1;

    printf("Second sort:\n");


    for(i=0; i<dim; i++)
        printf("%d ",array[i].peso);

    printf("\n");

    qsort(array, dim, sizeof(array[0]), comp);

    for(i=0; i<dim; i++)
        printf("%d ",array[i].peso);




    printf("\n");

}

My comp function:

int comp(const void* a, const void* b)
{
    aresta_* a1 = (aresta_*)a;
    aresta_* b1 = (aresta_*)b;
    return a1->peso > b1->peso;
}

The Output:

First sort:
1 6 2 3 
1 2 3 6 

Second sort:
1 2 3 6 1 5 1 
6 2 3 1 1 5 1 
Program ended with exit code: 0

Where did I go wrong? Any help would be greatly appreciated.

Answer 1

OP's function only returned 0 and 1. @Weather Vane

As this "worked" for OP for the first 4 values is "luck".

The compare function needs to return 1 of 3 results: negative, 0 or positive.

The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.
C11dr §7.22.5.2 3

int comp(const void* a, const void* b)
{
    const aresta_* a1 = (const aresta_*)a;
    const aresta_* b1 = (const aresta_*)b;
    // return a1->peso > b1->peso;
    return (a1->peso > b1->peso) - (a1->peso < b1->peso);
}

return (a1->peso > b1->peso) - (a1->peso < b1->peso); has advantages over return a1->peso - b1->peso;. This answer does not overflow. It is valid and functionally correct for all pairs of int. Various compilers recognize this idiom and produce tight code. int - int can overflow which is undefined behavior, UB.

Answer 2

int comp(const void* a, const void* b)
{
    aresta_* a1 = (aresta_*)a;
    aresta_* b1 = (aresta_*)b;
    ---->   return a1->peso > b1->peso;  <---- Watch carefully out! What it does!
}

The return line just checks merely greater or not. If,

• a1->peso is greater, it returns 1
• b1->peso is greater, it returns 0 (It is also not right result because zero must mean equal)
• What about equality case that the values equal each other?

You didn't check the last case. To do you can write with if-else cases like

if(a1->peso > b1->peso) {
//  ....
} else if (a1->peso < b1->peso) {
// ....
} else {
// equality case....
}

or simply do return a1->peso - b1->peso giving expected result that

• > 0 so positive
• < 0 so negative
• == 0 so equal each other

---

According to chux nicely drawing attention to overflow point, it can be handled for overflow case.

#include <limits.h>

if ((b1->peso > 0 && a1->peso < INT_MIN + b1->peso) ||
      (b1->peso < 0 && a1->peso > INT_MAX + b1->peso)) {
    /* Handle error */
} else {
    return a1->peso - b1->peso;
}