xref: /freebsd/lib/libc/stdlib/qsort.3 (revision eca67d510483ad9565b7b816e16fc72ebe3b2864) 
1.\" Copyright (c) 1990, 1991, 1993
2.\"	The Regents of the University of California.  All rights reserved.
3.\"
4.\" This code is derived from software contributed to Berkeley by
5.\" the American National Standards Committee X3, on Information
6.\" Processing Systems.
7.\"
8.\" Redistribution and use in source and binary forms, with or without
9.\" modification, are permitted provided that the following conditions
10.\" are met:
11.\" 1. Redistributions of source code must retain the above copyright
12.\"    notice, this list of conditions and the following disclaimer.
13.\" 2. Redistributions in binary form must reproduce the above copyright
14.\"    notice, this list of conditions and the following disclaimer in the
15.\"    documentation and/or other materials provided with the distribution.
16.\" 3. All advertising materials mentioning features or use of this software
17.\"    must display the following acknowledgement:
18.\"	This product includes software developed by the University of
19.\"	California, Berkeley and its contributors.
20.\" 4. Neither the name of the University nor the names of its contributors
21.\"    may be used to endorse or promote products derived from this software
22.\"    without specific prior written permission.
23.\"
24.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34.\" SUCH DAMAGE.
35.\"
36.\"     @(#)qsort.3	8.1 (Berkeley) 6/4/93
37.\" $FreeBSD$
38.\"
39.Dd September 7, 2002
40.Dt QSORT 3
41.Os
42.Sh NAME
43.Nm qsort , qsort_r , heapsort , mergesort
44.Nd sort functions
45.Sh LIBRARY
46.Lb libc
47.Sh SYNOPSIS
48.In stdlib.h
49.Ft void
50.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
51.Ft void
52.Fo qsort_r
53.Fa "void *base"
54.Fa "size_t nmemb"
55.Fa "size_t size"
56.Fa "void *thunk"
57.Fa "int (*compar)(void *, const void *, const void *)"
58.Fc
59.Ft int
60.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
61.Ft int
62.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
63.Sh DESCRIPTION
64The
65.Fn qsort
66function is a modified partition-exchange sort, or quicksort.
67The
68.Fn heapsort
69function is a modified selection sort.
70The
71.Fn mergesort
72function is a modified merge sort with exponential search
73intended for sorting data with pre-existing order.
74.Pp
75The
76.Fn qsort
77and
78.Fn heapsort
79functions sort an array of
80.Fa nmemb
81objects, the initial member of which is pointed to by
82.Fa base .
83The size of each object is specified by
84.Fa size .
85.Fn Mergesort
86behaves similarly, but
87.Em requires
88that
89.Fa size
90be greater than
91.Dq "sizeof(void *) / 2" .
92.Pp
93The contents of the array
94.Fa base
95are sorted in ascending order according to
96a comparison function pointed to by
97.Fa compar ,
98which requires two arguments pointing to the objects being
99compared.
100.Pp
101The comparison function must return an integer less than, equal to, or
102greater than zero if the first argument is considered to be respectively
103less than, equal to, or greater than the second.
104.Pp
105The
106.Fn qsort_r
107function behaves identically to
108.Fn qsort ,
109except that it takes an additional argument,
110.Fa thunk ,
111which is passed unchanged as the first argument to function pointed to
112.Fa compar .
113This allows the comparison function to access additional
114data without using global variables, and thus
115.Fn qsort_r
116is suitable for use in functions which must be reentrant.
117.Pp
118The algorithms implemented by
119.Fn qsort ,
120.Fn qsort_r ,
121and
122.Fn heapsort
123are
124.Em not
125stable, that is, if two members compare as equal, their order in
126the sorted array is undefined.
127The
128.Fn mergesort
129algorithm is stable.
130.Pp
131The
132.Fn qsort
133and
134.Fn qsort_r
135functions are an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
136a variant of partition-exchange sorting; in particular, see D.E. Knuth's
137Algorithm Q.
138.Sy Quicksort
139takes O N lg N average time.
140This implementation uses median selection to avoid its
141O N**2 worst-case behavior.
142.Pp
143The
144.Fn heapsort
145function is an implementation of J.W.J. William's ``heapsort'' algorithm,
146a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
147.Sy Heapsort
148takes O N lg N worst-case time.
149Its
150.Em only
151advantage over
152.Fn qsort
153is that it uses almost no additional memory; while
154.Fn qsort
155does not allocate memory, it is implemented using recursion.
156.Pp
157The function
158.Fn mergesort
159requires additional memory of size
160.Fa nmemb *
161.Fa size
162bytes; it should be used only when space is not at a premium.
163.Fn Mergesort
164is optimized for data with pre-existing order; its worst case
165time is O N lg N; its best case is O N.
166.Pp
167Normally,
168.Fn qsort
169is faster than
170.Fn mergesort
171is faster than
172.Fn heapsort .
173Memory availability and pre-existing order in the data can make this
174untrue.
175.Sh RETURN VALUES
176The
177.Fn qsort
178and
179.Fn qsort_r
180functions
181return no value.
182.Pp
183.Rv -std heapsort mergesort
184.Sh ERRORS
185The
186.Fn heapsort
187and
188.Fn mergesort
189functions succeed unless:
190.Bl -tag -width Er
191.It Bq Er EINVAL
192The
193.Fa size
194argument is zero, or,
195the
196.Fa size
197argument to
198.Fn mergesort
199is less than
200.Dq "sizeof(void *) / 2" .
201.It Bq Er ENOMEM
202.Fn Heapsort
203or
204.Fn mergesort
205were unable to allocate memory.
206.El
207.Sh COMPATIBILITY
208Previous versions of
209.Fn qsort
210did not permit the comparison routine itself to call
211.Fn qsort 3 .
212This is no longer true.
213.Sh SEE ALSO
214.Xr sort 1 ,
215.Xr radixsort 3
216.Rs
217.%A Hoare, C.A.R.
218.%D 1962
219.%T "Quicksort"
220.%J "The Computer Journal"
221.%V 5:1
222.%P pp. 10-15
223.Re
224.Rs
225.%A Williams, J.W.J
226.%D 1964
227.%T "Heapsort"
228.%J "Communications of the ACM"
229.%V 7:1
230.%P pp. 347-348
231.Re
232.Rs
233.%A Knuth, D.E.
234.%D 1968
235.%B "The Art of Computer Programming"
236.%V Vol. 3
237.%T "Sorting and Searching"
238.%P pp. 114-123, 145-149
239.Re
240.Rs
241.%A Mcilroy, P.M.
242.%T "Optimistic Sorting and Information Theoretic Complexity"
243.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
244.%V January 1992
245.Re
246.Rs
247.%A Bentley, J.L.
248.%T "Engineering a Sort Function"
249.%J "bentley@research.att.com"
250.%V January 1992
251.Re
252.Sh STANDARDS
253The
254.Fn qsort
255function
256conforms to
257.St -isoC .
258