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