Photo by Glenn Carstens-Peters on Unsplash
qsort, qsort_r, qsort_s
Comparison of different qsort functions
Overview
Quick-sort algorithm or qsort, sorting algorithm for arrays. It takes a function pointer and a user-definable comparison function containing the sorting routine. The function is an example of polymorphism since it enables the sorting of any kind of array elements, in ascending or descending order. The comparison function has two arguments that point to the objects being compared. qsort() calls the comparator function multiple times during the sort, and passes pointers to two array elements on each call.
The function qsort(), per se, is re-entrant and thread-safe function, as it does not require any global state. However, since the comparator function of qsort() only takes 2 pointers, any additional parameter to be passed to the comparator function would be a global variable. This is not thread-safe anymore, unless thread-specific data is used. [1]
Therefore, extensions of qsort() have been introduced. There are at least 5 different versions of qsort functions in C:
- qsort(), is a POSIX version, standardized C99
- qsort_s(), where _s stands for secure, is either the Windows version and a version defined by 2007 ISO ([2])
- qsort_r(), where _s stands for re-entrant, is a BSD/GNU Unix-like version (glibc version 2.8)
- qsort_b, where _b stands for blocks, for macOS and FreeBSD
Main differences:
- qsort() comparator function only takes 2 pointers
- qsort_r(), qsort_s() take an additional argument and pass it into the compare function
qsort_r is a non-standard function. It would be nice if it were standard, but you can't rely on that. qsort_s is sort of standard in C11 Annex K, but nobody really implements C11, let alone its annexes (Stack Overflow user Downvoter, [3])
qsort()
Declaration of qsort() ([4]):
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
The qsort() function sorts an array with nmemb elements of size size. The base argument points to the start of the array. The argument compar points to the comparison function.
The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second. If two elements are equal, their order is unspecified.
qsort_r()
Declaration of qsort_r() ([4]):
void qsort_r(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *, void *),
void *arg);
The qsort_r() function is identical to qsort() except that the comparison function compar takes a third argument. A pointer is passed to the comparison function via arg.
In this way, the comparison function does not need to use global variables to pass through arbitrary arguments, and is therefore reentrant and safe to use in threads.
qsort_s()
Introduced by Microsoft in VS 2005.
Declaration of qsort_s() ([5]):
void qsort_s(
void *base,
size_t num,
size_t width,
int (__cdecl *compare )(void *, const void *, const void *),
void * context
);
The pointer to a context, passed to qsort_s, can be any object that the compare routine needs to access via its third argument.
Known issues
- in GNU C library glibc the argument order was permuted w.r.t. BSD ([6])
Other publicly available versions
- a portable version of qsort_r/qsort_s https://github.com/noporpoise/sort_r
Sources
[1] How portable is the re-entrant qsort_r function
[3] Different declarations of qsort_r
[4] qsort and qsort_r man page
[5] qsort_s