xref: /dragonfly/lib/libc/stdlib/qsort.3 (revision b40e316c) 
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: src/lib/libc/stdlib/qsort.3,v 1.4.2.5 2001/12/14 18:33:58 ru Exp $
38.\" $DragonFly: src/lib/libc/stdlib/qsort.3,v 1.2 2003/06/17 04:26:46 dillon Exp $
39.\"
40.Dd June 4, 1993
41.Dt QSORT 3
42.Os
43.Sh NAME
44.Nm qsort , heapsort , mergesort
45.Nd sort functions
46.Sh LIBRARY
47.Lb libc
48.Sh SYNOPSIS
49.In stdlib.h
50.Ft void
51.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
52.Ft int
53.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
54.Ft int
55.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
56.Sh DESCRIPTION
57The
58.Fn qsort
59function is a modified partition-exchange sort, or quicksort.
60The
61.Fn heapsort
62function is a modified selection sort.
63The
64.Fn mergesort
65function is a modified merge sort with exponential search
66intended for sorting data with pre-existing order.
67.Pp
68The
69.Fn qsort
70and
71.Fn heapsort
72functions sort an array of
73.Fa nmemb
74objects, the initial member of which is pointed to by
75.Fa base .
76The size of each object is specified by
77.Fa size .
78.Fn Mergesort
79behaves similarly, but
80.Em requires
81that
82.Fa size
83be greater than
84.Dq "sizeof(void *) / 2" .
85.Pp
86The contents of the array
87.Fa base
88are sorted in ascending order according to
89a comparison function pointed to by
90.Fa compar ,
91which requires two arguments pointing to the objects being
92compared.
93.Pp
94The comparison function must return an integer less than, equal to, or
95greater than zero if the first argument is considered to be respectively
96less than, equal to, or greater than the second.
97.Pp
98The functions
99.Fn qsort
100and
101.Fn heapsort
102are
103.Em not
104stable, that is, if two members compare as equal, their order in
105the sorted array is undefined.
106The function
107.Fn mergesort
108is stable.
109.Pp
110The
111.Fn qsort
112function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
113a variant of partition-exchange sorting; in particular, see D.E. Knuth's
114Algorithm Q.
115.Fn Qsort
116takes O N lg N average time.
117This implementation uses median selection to avoid its
118O N**2 worst-case behavior.
119.Pp
120The
121.Fn heapsort
122function is an implementation of J.W.J. William's ``heapsort'' algorithm,
123a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
124.Fn Heapsort
125takes O N lg N worst-case time.
126Its
127.Em only
128advantage over
129.Fn qsort
130is that it uses almost no additional memory; while
131.Fn qsort
132does not allocate memory, it is implemented using recursion.
133.Pp
134The function
135.Fn mergesort
136requires additional memory of size
137.Fa nmemb *
138.Fa size
139bytes; it should be used only when space is not at a premium.
140.Fn Mergesort
141is optimized for data with pre-existing order; its worst case
142time is O N lg N; its best case is O N.
143.Pp
144Normally,
145.Fn qsort
146is faster than
147.Fn mergesort
148is faster than
149.Fn heapsort .
150Memory availability and pre-existing order in the data can make this
151untrue.
152.Sh RETURN VALUES
153The
154.Fn qsort
155function
156returns no value.
157.Pp
158.Rv -std heapsort mergesort
159.Sh ERRORS
160The
161.Fn heapsort
162and
163.Fn mergesort
164functions succeed unless:
165.Bl -tag -width Er
166.It Bq Er EINVAL
167The
168.Fa size
169argument is zero, or,
170the
171.Fa size
172argument to
173.Fn mergesort
174is less than
175.Dq "sizeof(void *) / 2" .
176.It Bq Er ENOMEM
177.Fn Heapsort
178or
179.Fn mergesort
180were unable to allocate memory.
181.El
182.Sh COMPATIBILITY
183Previous versions of
184.Fn qsort
185did not permit the comparison routine itself to call
186.Fn qsort 3 .
187This is no longer true.
188.Sh SEE ALSO
189.Xr sort 1 ,
190.Xr radixsort 3
191.Rs
192.%A Hoare, C.A.R.
193.%D 1962
194.%T "Quicksort"
195.%J "The Computer Journal"
196.%V 5:1
197.%P pp. 10-15
198.Re
199.Rs
200.%A Williams, J.W.J
201.%D 1964
202.%T "Heapsort"
203.%J "Communications of the ACM"
204.%V 7:1
205.%P pp. 347-348
206.Re
207.Rs
208.%A Knuth, D.E.
209.%D 1968
210.%B "The Art of Computer Programming"
211.%V Vol. 3
212.%T "Sorting and Searching"
213.%P pp. 114-123, 145-149
214.Re
215.Rs
216.%A Mcilroy, P.M.
217.%T "Optimistic Sorting and Information Theoretic Complexity"
218.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
219.%V January 1992
220.Re
221.Rs
222.%A Bentley, J.L.
223.%T "Engineering a Sort Function"
224.%J "bentley@research.att.com"
225.%V January 1992
226.Re
227.Sh STANDARDS
228The
229.Fn qsort
230function
231conforms to
232.St -isoC .
233