qsort

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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[edit]

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[edit]

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[edit]

  1. ^ a b c d 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. ^ a b "qsort(III), from UNIX Programmer's Manual, Third Edition". Unix Archive.
  4. ^ "qsort(III), from UNIX Programmer's Manual, Sixth Edition". Unix Archive.