xref: /freebsd/lib/libc/stdlib/qsort.3 (revision d37ea99837e6ad50837fd9fe1771ddf1c3ba6002) 
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 30, 2003
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.Fo qsort
51.Fa "void *base"
52.Fa "size_t nmemb"
53.Fa "size_t size"
54.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
55.Fc
56.Ft void
57.Fo qsort_r
58.Fa "void *base"
59.Fa "size_t nmemb"
60.Fa "size_t size"
61.Fa "void *thunk"
62.Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
63.Fc
64.Ft int
65.Fo heapsort
66.Fa "void *base"
67.Fa "size_t nmemb"
68.Fa "size_t size"
69.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
70.Fc
71.Ft int
72.Fo mergesort
73.Fa "void *base"
74.Fa "size_t nmemb"
75.Fa "size_t size"
76.Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
77.Fc
78.Sh DESCRIPTION
79The
80.Fn qsort
81function is a modified partition-exchange sort, or quicksort.
82The
83.Fn heapsort
84function is a modified selection sort.
85The
86.Fn mergesort
87function is a modified merge sort with exponential search
88intended for sorting data with pre-existing order.
89.Pp
90The
91.Fn qsort
92and
93.Fn heapsort
94functions sort an array of
95.Fa nmemb
96objects, the initial member of which is pointed to by
97.Fa base .
98The size of each object is specified by
99.Fa size .
100The
101.Fn mergesort
102function
103behaves similarly, but
104.Em requires
105that
106.Fa size
107be greater than
108.Dq "sizeof(void *) / 2" .
109.Pp
110The contents of the array
111.Fa base
112are sorted in ascending order according to
113a comparison function pointed to by
114.Fa compar ,
115which requires two arguments pointing to the objects being
116compared.
117.Pp
118The comparison function must return an integer less than, equal to, or
119greater than zero if the first argument is considered to be respectively
120less than, equal to, or greater than the second.
121.Pp
122The
123.Fn qsort_r
124function behaves identically to
125.Fn qsort ,
126except that it takes an additional argument,
127.Fa thunk ,
128which is passed unchanged as the first argument to function pointed to
129.Fa compar .
130This allows the comparison function to access additional
131data without using global variables, and thus
132.Fn qsort_r
133is suitable for use in functions which must be reentrant.
134.Pp
135The algorithms implemented by
136.Fn qsort ,
137.Fn qsort_r ,
138and
139.Fn heapsort
140are
141.Em not
142stable, that is, if two members compare as equal, their order in
143the sorted array is undefined.
144The
145.Fn mergesort
146algorithm is stable.
147.Pp
148The
149.Fn qsort
150and
151.Fn qsort_r
152functions are an implementation of C.A.R. Hoare's
153.Dq quicksort
154algorithm,
155a variant of partition-exchange sorting; in particular, see D.E. Knuth's
156Algorithm Q.
157.Sy Quicksort
158takes O N lg N average time.
159This implementation uses median selection to avoid its
160O N**2 worst-case behavior.
161.Pp
162The
163.Fn heapsort
164function is an implementation of J.W.J. William's
165.Dq heapsort
166algorithm,
167a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
168.Sy Heapsort
169takes O N lg N worst-case time.
170Its
171.Em only
172advantage over
173.Fn qsort
174is that it uses almost no additional memory; while
175.Fn qsort
176does not allocate memory, it is implemented using recursion.
177.Pp
178The function
179.Fn mergesort
180requires additional memory of size
181.Fa nmemb *
182.Fa size
183bytes; it should be used only when space is not at a premium.
184The
185.Fn mergesort
186function
187is optimized for data with pre-existing order; its worst case
188time is O N lg N; its best case is O N.
189.Pp
190Normally,
191.Fn qsort
192is faster than
193.Fn mergesort
194is faster than
195.Fn heapsort .
196Memory availability and pre-existing order in the data can make this
197untrue.
198.Sh RETURN VALUES
199The
200.Fn qsort
201and
202.Fn qsort_r
203functions
204return no value.
205.Pp
206.Rv -std heapsort mergesort
207.Sh ERRORS
208The
209.Fn heapsort
210and
211.Fn mergesort
212functions succeed unless:
213.Bl -tag -width Er
214.It Bq Er EINVAL
215The
216.Fa size
217argument is zero, or,
218the
219.Fa size
220argument to
221.Fn mergesort
222is less than
223.Dq "sizeof(void *) / 2" .
224.It Bq Er ENOMEM
225The
226.Fn heapsort
227or
228.Fn mergesort
229functions
230were unable to allocate memory.
231.El
232.Sh COMPATIBILITY
233Previous versions of
234.Fn qsort
235did not permit the comparison routine itself to call
236.Fn qsort 3 .
237This is no longer true.
238.Sh SEE ALSO
239.Xr sort 1 ,
240.Xr radixsort 3
241.Rs
242.%A Hoare, C.A.R.
243.%D 1962
244.%T "Quicksort"
245.%J "The Computer Journal"
246.%V 5:1
247.%P pp. 10-15
248.Re
249.Rs
250.%A Williams, J.W.J
251.%D 1964
252.%T "Heapsort"
253.%J "Communications of the ACM"
254.%V 7:1
255.%P pp. 347-348
256.Re
257.Rs
258.%A Knuth, D.E.
259.%D 1968
260.%B "The Art of Computer Programming"
261.%V Vol. 3
262.%T "Sorting and Searching"
263.%P pp. 114-123, 145-149
264.Re
265.Rs
266.%A McIlroy, P.M.
267.%T "Optimistic Sorting and Information Theoretic Complexity"
268.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
269.%V January 1992
270.Re
271.Rs
272.%A Bentley, J.L.
273.%A McIlroy, M.D.
274.%T "Engineering a Sort Function"
275.%J "Software--Practice and Experience"
276.%V Vol. 23(11)
277.%P pp. 1249-1265
278.%D November\ 1993
279.Re
280.Sh STANDARDS
281The
282.Fn qsort
283function
284conforms to
285.St -isoC .
286