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]

History

A qsort function was implemented by Lee McMahon in 1972.[3][1] It was in place in Version 3 Unix as a library function, 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 for BSD.[1] The function was standardized in ANSI C (1989).

In 1991, Bell Labs employees observed that McMahon's 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.[1]

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;
    // All the logic is often alternatively written:
    return (x > y) - (x < y);
}

/* 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);
}

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.