qsort Comparison Function
C
In C, the qsort()
function sorts an array in place using the quickersort algorithm - a variation of quick sort.
Function Signature
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
Function arguments for qsort()
:
base
: pointer to the start of the arraynmemb
: Number of members in the arraysize
: Size of an individual element in the arraycompar
: Pointer to a comparison function that accepts 2 xconst void *
arguments
To use qsort()
, you need to include the stdlib.h header - i.e. #include <stdlib.h>
.
Comparison Function
The comparison function must return an integer that is:
- Less than zero if the first argument is considered to be less than the second
- Zero if the arguments are equal
- Greater than zero if the first argument is considered to be greater than the second
Be careful with return values - especially if the values being compared are not integers.
Use >
or ‘<’ rather than subtraction which may provide unexpected results if comparing non integer values.
Note that the comparison function receives const void *
as arguments - and you may need to cast these within the comparison function.
Example
typedef struct triangle
{
int a;
int b;
int c;
} Triangle;
int compareTriangles(const void *x, const void *y)
{
const Triangle *a = x, *b = y;
int res = area(a) != area(b) ? area(a) > area(b) ? 1 : -1 : 0;
return res;
}
/**
* Sort an array of Triangles
*/
void sort_by_area(Triangle* tr, int n) {
qsort(tr, n, sizeof(Triangle), compareTriangles);
}
The above example sorts an array of Triangle
type defined objects according to area (area()
has been omitted for brevity).
Note the nested conditional in compareTriangles()
:
- If area of a and b are not equal, return 1 if the area of a is greater than the area of b, -1 if not.
- If the area of a and b are equal, return 0.
Also note the line const Triangle *a = x, *b = y;
which copies the input pointers into the object required for the comparison.
Pointer Conversion in Comparator Function
The comparator function receives const void *
type pointers - these should be cast in the comparator to the original type of the data passed in.
Multiple Indirection: Double Pointers
If the comparator function for qsort compares values in an array of pointers (pointer-to-pointer), cast to this within the comparator.
For example, if the array to be sorted is an array of pointers, the comparator should cast the input void pointers to pointer to the underlying type pointer.
The code below shows how an array of pointers to custom card_t
types is sorted:
/**
* Comparator function to sort an array of type card_t *
* card_t is a typedef defined struct, with value and suit (numeric) fields.
*
*/
int card_ptr_comp(const void *inPtr1, const void *inPtr2)i
{
const card_t *c1 = *(const card_t **)inPtr1;
const card_t *c2 = *(const card_t **)inPtr2;
unsigned v1 = c1->value;
unsigned v2 = c2->value;
// Alternative way of handling the cast:
// const card_t * const *c1 = inPtr1;
// const card_t * const *c2 = inPtr2;
// unsigned v1 = (*c1)->value;
// unsigned v2 = (*c2)->value;
if (v1 != v2)
return (v1 > v2) ? -1 : (v1 == v2) ? 0 : 1;
else
return (c1->suit > c2->suit) ? -1 : 1;
}
int main()
{
card_t **cards = malloc(n * sizeof(card_t*));
// ... add cards
qsort(cards, n_cards, sizeof(cards[0]), card_ptr_comp);
// ... free dynbamically allocated resources
return 0;
}
More complete example:
#include <stdio.h>
#include <stdlib.h>
typedef struct person {
int id;
const char *name;
} person_t;
// Compare by id
int comparePeople(const void *inPtr1, const void *inPtr2)
{
const person_t *p1 = *(const person_t**)inPtr1;
const person_t *p2 = *(const person_t**)inPtr2;
if (p1->id != p2->id)
return p1->id > p2->id ? 1 : -1;
return 0;
}
int main()
{
person_t a = {99, "Alice"};
person_t b = {42, "Bob"};
person_t c = {33, "Chris"};
person_t *people[] = {&a, &b, &c};
qsort(people, sizeof(people) / sizeof(people[0]), sizeof(people[0]), comparePeople);
for (size_t i = 0; i < sizeof(people) / sizeof(people[0]); i++) {
printf("id: %d\tname: %s\n", people[i]->id, people[i]->name);
}
return 0;
}
comments powered by Disqus