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

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 ar开发者_如何转开发ray.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

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

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;

}

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;
 }

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;
}

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.