qsort

qsort is a C standard library function that implements a polymorphic sorting algorithm for arrays of arbitrary objects according to a user-provided comparison function. It is named after the "quicker sort" algorithm (a quicksort variant due to R. S. Scowen), which was originally used to implement it in the Unix C library, although the C standard does not require it to implement quicksort.^[1]

Implementations of the qsort function achieve polymorphism by taking a function pointer to a three-way comparison function, as well as a parameter that specifies the size of its individual input objects. The C standard requires the comparison function to implement a total order on the items in the input array.^[2]

A qsort function was in place in Version 3 Unix of 1973, but was then an assembler subroutine.^[3] A C version, with roughly the interface of the standard C version, was in-place in Version 6 Unix.^[4] It was rewritten in 1983 at Berkeley.^[1] The function was standardized in ANSI C (1989).

Example

The following piece of C code shows how to sort a list of integers using qsort.

#include <stdlib.h>
 
/* Comparison function. Receives two generic (void) pointers. */
int compare(const void *p, const void *q)
{
    int x = *(const int *)p;
    int y = *(const int *)q;
    /* to avoid undefined behaviour through signed integer overflow,
        avoid: return x - y; */
    int ret;
    if (x == y)
      ret = 0;
    else
      ret = (x < y) ? -1 : 1;
 
    return ret;
}
 
/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n)
{
    qsort(a, n, sizeof(int), compare);
}

References