problem by ordering a data structure using the qsort function in C

Question

I need to order a array of data structure that contains information relating to a node origin, destination and weight. the problem is not ordered properly, because if two values are equal to array.originNode simply takes the first value you get and not as it should be ordered.

This is how my code does order the structure

0 1 30
1 3 22
2 3 20
3 5 20
3 4 15

Process returned 0 (0x0)   execution time : 0.015 s

Here's how it should order

I think the problem is the function that I am passing as parameter to qsort, which is not making the correct comparison. How do I change my comparison function to my code sorts the array of struct properly?

this is my full code

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

 typedef struct dataNodes{
   int originNode;
   int destinationNode;
   int weight;
   struct dataNodes *next;
} ARRAYS;


  int function (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}


int main() {
ARRAYS array[6];
int n = 5, i;

array [0].originNode = 3;
array [1].originNode = 3;
array[2].originNode = 1;
array[3].originNode = 0;
array[4].originNode = 2;


array [0].destinationNode = 4 ;
array [1].destinationNode = 5;
array[2].destinationNode = 3;
array[3].destinationNode = 1;
array[4].destinationNode = 3;


array [0].weight = 15;
array [1].weight = 20;
array[2].weight = 22;
array[3].weight = 30;
array[4].weight = 20;


              qsort(array,n,sizeof(array[0]),function);
    for(i=0; i<n; i++)
    {
    printf("%d %d %d\n",array[i].originNode,array[i].destinationNode,
    array[i].weight);
    }
return 0;

}

Of course the type of parameter that I am passing the function is void *, initially thought to pass the data type of the structure, but do not understand how to compare. — franvergara66, Jul 12 '11 at 04:28

Sodved · Accepted Answer · 2011-07-12T07:02:01.830

3

You need to change your compare function to compare ARRAY records properly. First compare originNode, and if they're the same compare destinationNode.

int function (const void * a, const void * b)
{
    const ARRAYS *ap = a;
    const ARRAYS *bp = b;
    if( ap->originNode < bp->originNode )
        return -1;
    else if( ap->originNode > bp->originNode )
        return 1;
    else if( ap->destinationNode < bp->destinationNode )
        return -1;
    else if( ap->destinationNode > bp->destinationNode )
        return 1;
    else
        return 0;
 }

edited Jul 12 '11 at 07:02

answered Jul 12 '11 at 04:46

Sodved

8,428
2
31
43

2

You don't need the cast: `ARRAYS *ap = a;` is fine. – Alok Singhal Jul 12 '11 at 04:55
1

@Alok: Actually the cast is necessary due to the fact that Sodved's code is removing the `const` qualifier. If the types were fixed to be `const ARRAYS *` then the cast could be omitted. – R.. GitHub STOP HELPING ICE Jul 12 '11 at 05:25
@R. true, although ideally `ap` and `bp` should be `const ARRAYS *`. – Alok Singhal Jul 12 '11 at 06:15
Thanks fellas (@R and @Alok), have made the suggested changes to the answer. – Sodved Jul 12 '11 at 07:02

score 2 · Answer 2 · answered Jul 12 '11 at 04:47

You are sorting an array of (uh...) ARRAYS. So your sort function that you pass in should be comparing ARRAYS objects. Your code treats it as int's.

To do secondary sorting, you need to compare the corresponding secondary fields in the case that the primary fields are equal. Do the same for any more fields you want to compare.

So in your case, this sort function could work for you:

int sort_ARRAYS (const void * a, const void * b)
{
    /* the arguments are pointers to ARRAYS objects */
    const ARRAYS *x = a;
    const ARRAYS *y = b;
    int cmp;

    /* primary */
    cmp = x->originNode - y->originNode;
    if (cmp != 0) return cmp;

    /* secondary */
    cmp = x->destinationNode - y->destinationNode;
    if (cmp != 0) return cmp;

    /* tertiary */
    return x->weight - y->weight;
}

score 0 · Answer 3 · answered Jul 12 '11 at 04:46

From the fine manual:

void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
[...]
The compar argument is a pointer to the comparison function, which is called with two arguments that point to the elements being compared.

So your comparison function will receive two ARRAY * arguments disguised as const void * and your function just needs to cast them appropriately:

int
function(const void * a, const void * b) {
    ARRAYS *aa = (ARRAYS *)a;
    ARRAYS *bb = (ARRAYS *)b;
    return aa->originNode - bb->originNode;
}

If you want a secondary sort key, then check if aa->originNode == bb->originNode and compare the secondary key if that's true; similarly for the tertiary key if needed.

Your current code is working by accident. This:

return ( *(int*)a - *(int*)b );

is actually comparing the first elements of the ARRAYS* arguments and it works because (a) there's no padding at the beginning of your structure and (b) originNode is at the beginning and it actually is an int.

problem by ordering a data structure using the qsort function in C

3 Answers3