Main index | Section 3 | 日本語 | Deutsch | Options |

Standard C Library (libc, -lc)

#include <stdlib.h>

The
`qsort()`
function is a modified partition-exchange sort, or quicksort.
The
`heapsort()`
function is a modified selection sort.
The
`mergesort()`
function is a modified merge sort with exponential search
intended for sorting data with pre-existing order.

The
`qsort()`
and
`heapsort()`
functions sort an array of
nmemb
objects, the initial member of which is pointed to by
base.
The size of each object is specified by
size.
The
`mergesort()`
function
behaves similarly, but
* requires*
that
size
be greater than
"sizeof(void *) / 2".

The contents of the array base are sorted in ascending order according to a comparison function pointed to by compar, which requires two arguments pointing to the objects being compared.

The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

The
`qsort_r()`
function behaves identically to
`qsort()`,
except that it takes an additional argument,
thunk,
which is passed unchanged as the first argument to function pointed to
compar.
This allows the comparison function to access additional
data without using global variables, and thus
`qsort_r()`
is suitable for use in functions which must be reentrant.
The
`qsort_b()`
function behaves identically to
`qsort()`,
except that it takes a block, rather than a function pointer.

The algorithms implemented by
`qsort()`,
`qsort_r()`,
and
`heapsort()`
are
* not*
stable, that is, if two members compare as equal, their order in
the sorted array is undefined.
The
`heapsort_b()`
function behaves identically to
`heapsort()`,
except that it takes a block, rather than a function pointer.
The
`mergesort()`
algorithm is stable.
The
`mergesort_b()`
function behaves identically to
`mergesort()`,
except that it takes a block, rather than a function pointer.

The
`qsort()`
and
`qsort_r()`
functions are an implementation of C.A.R.
Hoare's
"quicksort"
algorithm,
a variant of partition-exchange sorting; in particular, see
** D.E. Knuth's**
Algorithm Q.
** Quicksort**
takes O N lg N average time.
This implementation uses median selection to avoid its
O N**2 worst-case behavior.

The
`heapsort()`
function is an implementation of
** J.W.J. William's**
"heapsort"
algorithm,
a variant of selection sorting; in particular, see
** D.E. Knuth's**
Algorithm H.
** Heapsort**
takes O N lg N worst-case time.
Its
* only*
advantage over
`qsort()`
is that it uses almost no additional memory; while
`qsort()`
does not allocate memory, it is implemented using recursion.

The function
`mergesort()`
requires additional memory of size
nmemb, *
size
bytes; it should be used only when space is not at a premium.
The
`mergesort()`
function
is optimized for data with pre-existing order; its worst case
time is O N lg N; its best case is O N.

Normally,
`qsort()`
is faster than
`mergesort()`
is faster than
`heapsort()`.
Memory availability and pre-existing order in the data can make this
untrue.

The
`qsort()`
and
`qsort_r()`
functions
return no value.

The heapsortand mergesort functions return the value 0 if successful; otherwise the value -1 is returned and the global variable errno is set to indicate the error.

A sample program that sorts an array of
int
values in place using
`qsort()`,
and then prints the sorted array to standard output is:

#include <stdio.h> #include <stdlib.h>/* * Custom comparison function that compares 'int' values through pointers * passed by qsort(3). */ static int int_compare(const void *p1, const void *p2) { int left = *(const int *)p1; int right = *(const int *)p2;

return ((left > right) - (left < right)); }

/* * Sort an array of 'int' values and print it to standard output. */ int main(void) { int int_array[] = { 4, 5, 9, 3, 0, 1, 7, 2, 8, 6 }; size_t array_size = sizeof(int_array) / sizeof(int_array[0]); size_t k;

qsort(&int_array, array_size, sizeof(int_array[0]), int_compare); for (k = 0; k < array_size; k++) printf(" %d", int_array[k]); puts(""); return (EXIT_SUCCESS); }

Previous versions of
`qsort()`
did not permit the comparison routine itself to call
`qsort(3)`.
This is no longer true.

The
`heapsort()`
and
`mergesort()`
functions succeed unless:

[EINVAL]
| |

The
size
argument is zero, or,
the
size
argument to
mergesort()
is less than
"sizeof(void *) / 2".
| |

[ENOMEM]
| |

The
heapsort()
or
mergesort()
functions
were unable to allocate memory.
| |

sort(1),
radixsort(3)

The Computer Journal, pp. 10-15, Quicksort, 5:1, 1962.

,Communications of the ACM, pp. 347-348, Heapsort, 7:1, 1964.

,The Art of Computer Programming, pp. 114-123, 145-149, Sorting and Searching, Vol. 3, 1968.

,Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Optimistic Sorting and Information Theoretic Complexity, January 1992,

,Software--Practice and Experience, pp. 1249-1265, Engineering a Sort Function, Vol. 23(11), November_SPACE_1993.

, ,
The
`qsort()`
function
conforms to
ISO/IEC 9899:1990 ("ISO C90").

The variants of these functions that take blocks as arguments first appeared in
Mac OS X.
This implementation was created by David Chisnall.

QSORT (3) | February 20, 2013 |

Main index | Section 3 | 日本語 | Deutsch | Options |

Please direct any comments about this manual page service to Ben Bullock. Privacy policy.

“ | If you have an emergency I'm great at running around and flailing my arms | ” |

— Artur Bagyants |