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, the ability to sort different kinds of data, 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 to the items under comparison. */
int compare_ints(const void *p, const void *q) {
    int x = *(const int *)p;
    int y = *(const int *)q;

    /* Avoid return x - y, which can cause undefined behaviour
       because of signed integer overflow. */
    if (x < y)
        return -1;  // Return -1 if you want ascending, 1 if you want descending order. 
    else if (x > y)
        return 1;   // Return 1 if you want ascending, -1 if you want descending order. 

    return 0;
}

/* Sort an array of n integers, pointed to by a. */
void sort_ints(int *a, size_t n) {
    qsort(a, n, sizeof(*a), compare_ints);
}
gollark: `give me interior mutability as I'm literal beeoid`
gollark: `cache` is too specific. No.
gollark: UTF-32 fairly suboptimal?
gollark: Strings which are good have an invariant for UTF-8.
gollark: This allows O(something) random access.

References
  1. Bentley, Jon L.; McIlroy, M. Douglas (1993). "Engineering a sort function". Software—Practice and Experience. 23 (11): 1249–1265. CiteSeerX 10.1.1.14.8162. doi:10.1002/spe.4380231105.
  2. ISO/IEC 9899:201x, Programming Languages—C (draft). §7.22.5. November 16, 2010.
  3. "qsort(III), from UNIX Programmer's Manual, Third Edition". Unix Archive.
  4. "qsort(III), from UNIX Programmer's Manual, Sixth Edition". Unix Archive.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.