Dev Notes

Various Cheat Sheets and Resources by David Egan/Carawebs.

qsort Comparison Function


C
David Egan

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():

  1. base: pointer to the start of the array
  2. nmemb: Number of members in the array
  3. size: Size of an individual element in the array
  4. compar: Pointer to a comparison function that accepts 2 x const 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