Annotation of src/lib/libc/stdlib/qsort.3, Revision 1.6
1.6 ! perry 1: .\" $NetBSD: qsort.3,v 1.5 1997/11/14 02:04:55 mrg Exp $
1.4 thorpej 2: .\"
1.3 mycroft 3: .\" Copyright (c) 1990, 1991, 1993
4: .\" The Regents of the University of California. All rights reserved.
1.1 cgd 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: .\"
1.3 mycroft 38: .\" from: @(#)qsort.3 8.1 (Berkeley) 6/4/93
1.1 cgd 39: .\"
1.3 mycroft 40: .Dd June 4, 1993
1.1 cgd 41: .Dt QSORT 3
42: .Os
43: .Sh NAME
1.5 mrg 44: .Nm qsort ,
45: .Nm heapsort ,
46: .Nm mergesort
1.1 cgd 47: .Nd sort functions
1.6 ! perry 48: .Sh LIBRARY
! 49: .Lb libc
1.1 cgd 50: .Sh SYNOPSIS
51: .Fd #include <stdlib.h>
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 *)"
1.3 mycroft 56: .Ft int
57: .Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
1.1 cgd 58: .Sh DESCRIPTION
59: The
60: .Fn qsort
61: function is a modified partition-exchange sort, or quicksort.
62: The
63: .Fn heapsort
64: function is a modified selection sort.
1.3 mycroft 65: The
66: .Fn mergesort
67: function is a modified merge sort with exponential search
68: intended for sorting data with pre-existing order.
1.1 cgd 69: .Pp
70: The
71: .Fn qsort
72: and
73: .Fn heapsort
74: functions sort an array of
75: .Fa nmemb
76: objects, the initial member of which is pointed to by
77: .Fa base .
78: The size of each object is specified by
79: .Fa size .
1.3 mycroft 80: .Fn Mergesort
81: behaves similarly, but
82: .Em requires
83: that
84: .Fa size
85: be greater than
86: .Dq "sizeof(void *) / 2" .
1.1 cgd 87: .Pp
1.3 mycroft 88: The contents of the array
89: .Fa base
90: are sorted in ascending order according to
1.1 cgd 91: a comparison function pointed to by
92: .Fa compar ,
1.3 mycroft 93: which requires two arguments pointing to the objects being
1.1 cgd 94: compared.
95: .Pp
96: The comparison function must return an integer less than, equal to, or
97: greater than zero if the first argument is considered to be respectively
98: less than, equal to, or greater than the second.
99: .Pp
100: The functions
101: .Fn qsort
102: and
103: .Fn heapsort
104: are
105: .Em not
106: stable, that is, if two members compare as equal, their order in
107: the sorted array is undefined.
1.3 mycroft 108: The function
109: .Fn mergesort
110: is stable.
1.1 cgd 111: .Pp
112: The
113: .Fn qsort
114: function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
115: a variant of partition-exchange sorting; in particular, see D.E. Knuth's
116: Algorithm Q.
117: .Fn Qsort
118: takes O N lg N average time.
1.3 mycroft 119: This implementation uses median selection to avoid its
1.1 cgd 120: O N**2 worst-case behavior.
121: .Pp
122: The
123: .Fn heapsort
124: function is an implementation of J.W.J. William's ``heapsort'' algorithm,
125: a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
126: .Fn Heapsort
127: takes O N lg N worst-case time.
128: Its
129: .Em only
130: advantage over
131: .Fn qsort
1.3 mycroft 132: is that it uses almost no additional memory; while
133: .Fn qsort
134: does not allocate memory, it is implemented using recursion.
135: .Pp
136: The function
137: .Fn mergesort
138: requires additional memory of size
139: .Fa nmemb *
140: .Fa size
141: bytes; it should be used only when space is not at a premium.
142: .Fn Mergesort
143: is optimized for data with pre-existing order; its worst case
144: time is O N lg N; its best case is O N.
145: .Pp
146: Normally,
147: .Fn qsort
148: is faster than
149: .Fn mergesort
150: is faster than
151: .Fn heapsort .
152: Memory availability and pre-existing order in the data can make this
153: untrue.
1.1 cgd 154: .Sh RETURN VALUES
155: The
156: .Fn qsort
157: function
158: returns no value.
159: .Pp
160: Upon successful completion,
161: .Fn heapsort
1.3 mycroft 162: and
163: .Fn mergesort
164: return 0.
165: Otherwise, they return \-1 and the global variable
1.1 cgd 166: .Va errno
167: is set to indicate the error.
168: .Sh ERRORS
169: The
170: .Fn heapsort
171: function succeeds unless:
172: .Bl -tag -width Er
173: .It Bq Er EINVAL
174: The
175: .Fa size
1.3 mycroft 176: argument is zero, or,
177: the
178: .Fa size
179: argument to
180: .Fn mergesort
181: is less than
182: .Dq "sizeof(void *) / 2" .
183: .It Bq Er ENOMEM
184: .Fn Heapsort
185: or
186: .Fn mergesort
187: were unable to allocate memory.
188: .El
1.1 cgd 189: .Sh COMPATIBILITY
190: Previous versions of
191: .Fn qsort
1.3 mycroft 192: did not permit the comparison routine itself to call
1.1 cgd 193: .Fn qsort 3 .
194: This 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
1.3 mycroft 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
1.1 cgd 233: .Re
234: .Sh STANDARDS
235: The
236: .Fn qsort
237: function
238: conforms to
239: .St -ansiC .
CVSweb <webmaster@jp.NetBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to qsort.3 CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [cvs.NetBSD.org] / src / lib / libc / stdlib