QSORT

Section: C Library Functions (3)
Index Return to Main Contents

BSD mandoc
 

NAME

qsort, heapsort - sort functions  

SYNOPSIS

Fd #include <stdlib.h> Ft void Fn qsort void *base size_t nmemb size_t size int (*compar)(const void *, const void *) Ft int Fn heapsort void *base size_t nmemb size_t size int (*compar)(const void *, const void *)  

DESCRIPTION

The Fn qsort function is a modified partition-exchange sort, or quicksort. The Fn heapsort function is a modified selection sort.

The Fn qsort and Fn heapsort functions sort an array of Fa nmemb objects, the initial member of which is pointed to by Fa base . The size of each object is specified by Fa size .

The contents of the array are sorted in ascending order according to a comparison function pointed to by Fa compar , which is called with two arguments that point 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 functions Fn qsort and Fn heapsort are not stable, that is, if two members compare as equal, their order in the sorted array is undefined.

The Fn qsort function is 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. Fn Qsort takes O N lg N average time. This implementation uses median selection to avoid the traditional O N**2 worst-case behavior.

The Fn 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. Fn Heapsort takes O N lg N worst-case time. Its only advantage over Fn qsort is that it uses no additional memory.  

RETURN VALUES

The Fn qsort function returns no value.

Upon successful completion, Fn heapsort returns 0. Otherwise, it returns -1 and the global variable errno is set to indicate the error.  

ERRORS

The Fn heapsort function succeeds unless:

Bq Er EINVAL
The Fa size argument is zero.
 

COMPATIBILITY

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

SEE ALSO

sort(1), radixsort(3)
Hoare, C.A.R. 1962 "Quicksort" "The Computer Journal" 5:1 pp. 10-15
Williams, J.W.J 1964 "Heapsort" "Communications of the ACM" 7:1 pp. 347-348
Knuth, D.E. 1968 "The Art of Computer Programming" Vol. 3 "Sorting and Searching" pp. 114-123, 145-149
 

STANDARDS

The Fn qsort function conforms to St -ansiC .


 

Index

NAME
SYNOPSIS
DESCRIPTION
RETURN VALUES
ERRORS
COMPATIBILITY
SEE ALSO
STANDARDS

This document was created by man2html, using the manual pages.
Time: 06:42:53 GMT, May 19, 2025