Qsort function in C

how does the qsort function work in C

qsort( s , n , sizeof(struct coord) , compare );

how can one manipulate the compare function in qsort while sorting structure rather than a array like above
and how does changes in the compare function reflect in the overall sort result…

The compare function is expected to take two const void * arguments and return an int.

The arguments point to starting address of the data. It is up to the programmer to write code to compare the data in those locations, and return an integer value after comparison. If it returns a negative value, then the data pointed to by first argument will always appear before the data pointed to by second argument in the sorted array. And vice-versa.

typedef struct node {
    int id;
    char foo[255];
} Node;

int compare(const void * x, const void * y) {
    Node * a = (Node *) x;
    Node * b = (Node *) y;
    return a->id - b->id;
}

int main() {
    Node array[SIZE];
    int n;
    ...
    qsort(array, n, sizeof(Node), compare);
    ...
    return 0;
}

As a small example, the above code snippet will sort an array of n Nodes in the ascending order of their ids. You can add any complex logic in the compare function. In the end, if it returns negative, then the Node pointed to by x (or a) will appear before the other one in the sorted array; and vice-versa.

2 Likes

@damn_me, This was large enough to fit inside a comment. So, I am adding it as a separate answer, and not as a comment/reply to your comment.

Dereferencing means, trying to get to the data in the location pointed to by the pointer.

So, a = b; and b = a; are both valid. It is *a which is invalid, as you don’t kind of data a points to.

To throw more light on what I said, all kinds of pointer variables take up the same memory (i.e., sizeof(int *) == sizeof(char *) == sizeof(Node *)) The type of a pointer is only good to access the data it points to.

So, if you have a pointer variable p, and if you do a *p, then, it needs to know how many bytes of data from the memory address pointed to by p needs to be looked into. If the type of p is int *, then 4 bytes (assuming int takes 4-byte) of data is fetched/accessed/looked-into. If the type of p is char *, then 1 byte of data is looked-into. If the type of p is Node *, then 259 bytes (assuming that Node is the structure as defined in my first answer) of data is looked-into.

Now, imagine a void *p; If you do a *p, then it does not know how many bytes of data to look into. Hence, it is forbidden. But, if you cast it into an int * or a Node * or more generally, a <Type> *, then when you do a dereferencing on the type casted pointer, sizeof(<Type>) bytes starting from the memory location pointed to by it will be looked-into.

void pointers are usually used as a generic type. It is up to the programmer to properly type-cast it and then dereference the pointer when in need.

In the specific qsort example, this function expects a fourth argument, which is a pointer to a function (yes, there are pointer to functions, in case you didn’t already know – the name of the function is a pointer to itself). This function must return an integer after comparing two data items. Now, when defining the signature of qsort, it needs to specify what kind of function it expects. Since the fourth argument points to a function, it needs to specify what kind of function it points to (the signature of that function). For that, it needs to give the data types. If not for the generic void pointers, it would have been impossible in C to do this, as you would need separate declarations for each different data type you would expect qsort to sort (which also means, you will not be able to use qsort to sort custom data types) in addition to the added complexity that all those qsort functions need to be uniquely named (like qsort_int, qsort_char etc.)

From what I understood from your comment, I feel that you are confused about the basics of pointers. I hope this answer might clear up some of that. If you need more clarification/understanding, feel free to reply/ask.

Best regards,

Tijo

1 Like

@tijoforyou Just for clarification of what I know about this basic thing, using void *a(pointer a actually it is) means, declaring a generic pointer a i.e. a pointer which can be made to point to any other data type but that cannot be referenced. I.e if I do, int *b;(pointer b actually it is) then a=b is valid but b=a isn’t valid. So, const void *a means, once assigned a pointer to a, it cannot be modified further. Am I right??! Please correct me if I am wrong.

@tijoforyou Yeah, Was kind of confused! But got answers of certain things from Your post. Thanks :slight_smile:

However, can we use qsort in some way to sort an array of the type a[n][2] by its 0th coloumn value in increasing order and for same values of a[i][0], sort a[i][1] in decreasing order??