Qsort

A qsort function appears in Version 2 Unix in 1972 as a library assembly language subroutine. Its interface is unlike the modern version, in that it can be pseudo-prototyped as void qsort(void* start, void* end, unsigned int length) – sorting contiguously-stored -long byte strings from the range [, ). This, and the lack of a replaceable comparison function, makes it unsuitable to properly sort the system's little-endian integers, or any other data structures. In Version 3 Unix, the interface is extended by calling compar(III), with an interface identical to modern-day . This function may be overridden by the user's program to implement any kind of ordering, in an equivalent fashion to the compar argument to standard (though program-global, of course). Version 4 Unix adds a C implementation, with an interface equivalent to the standard. It was rewritten in 1983 for the Berkeley Software Distribution. In 1991, Bell Labs employees observed that AT&T and BSD versions of qsort would consume quadratic time for some simple inputs. Thus Jon Bentley and Douglas McIlroy engineered a new faster and more robust implementation. == Example ==

The following piece of C code shows how to sort a list of integers using qsort. • include // Comparison function. Receives two generic (void) pointers to the items under comparison. int compareInts(const void* p, const void* q) { int x = *(const int*)p; int y = *(const int*)q; // Avoid returning x - y, which can cause undefined behaviour // because of signed integer overflow. if (x y) { // Return +1 for ascending, -1 for descending order. return 1; } else { return 0; } } // This could be more concisely written as: int compareInts(const void* p, const void* q) { int x = *(const int*)p; int y = *(const int*)q; return (x > y) - (x == Extensions ==

Since the comparison function of the original qsort only accepts two pointers, passing in additional parameters (e.g. producing a comparison function that compares by the two value's difference with another value) must be done using global variables. The issue was solved by the BSD and GNU Unix-like systems by introducing a qsort_r function, which allows for an additional parameter to be passed to the comparison function. The two versions of qsort_r have different argument orders. C11 Annex K defines a qsort_s essentially identical to GNU's qsort_r. The macOS and FreeBSD libcs also contain qsort_b, a variant that uses blocks, an analogue to closures, as an alternate solution to the same problem. In C++, it is faster to use (or std::ranges::sort from C++20 and onwards). Compared to , the templated is more type-safe since it does not require access to data items through unsafe pointers, as does. Also, accesses the comparison function using a function pointer, necessitating large numbers of repeated function calls, whereas in , comparison functions may be inlined into the custom object code generated for a template instantiation. In practice, C++ code using is often considerably faster at sorting simple data like integers than equivalent C code using . == References ==