Commit | Line | Data |
---|---|---|
15637ed4 RG |
1 | .\" Copyright (c) 1990, 1991 The Regents of the University of California. |
2 | .\" 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 6.7 (Berkeley) 6/29/91 | |
37 | .\" | |
38 | .Dd June 29, 1991 | |
39 | .Dt QSORT 3 | |
40 | .Os | |
41 | .Sh NAME | |
42 | .Nm qsort, heapsort | |
43 | .Nd sort functions | |
44 | .Sh SYNOPSIS | |
45 | .Fd #include <stdlib.h> | |
46 | .Ft void | |
47 | .Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" | |
48 | .Ft int | |
49 | .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" | |
50 | .Sh DESCRIPTION | |
51 | The | |
52 | .Fn qsort | |
53 | function is a modified partition-exchange sort, or quicksort. | |
54 | The | |
55 | .Fn heapsort | |
56 | function is a modified selection sort. | |
57 | .Pp | |
58 | The | |
59 | .Fn qsort | |
60 | and | |
61 | .Fn heapsort | |
62 | functions sort an array of | |
63 | .Fa nmemb | |
64 | objects, the initial member of which is pointed to by | |
65 | .Fa base . | |
66 | The size of each object is specified by | |
67 | .Fa size . | |
68 | .Pp | |
69 | The contents of the array are sorted in ascending order according to | |
70 | a comparison function pointed to by | |
71 | .Fa compar , | |
72 | which is called with two arguments that point to the objects being | |
73 | compared. | |
74 | .Pp | |
75 | The comparison function must return an integer less than, equal to, or | |
76 | greater than zero if the first argument is considered to be respectively | |
77 | less than, equal to, or greater than the second. | |
78 | .Pp | |
79 | The functions | |
80 | .Fn qsort | |
81 | and | |
82 | .Fn heapsort | |
83 | are | |
84 | .Em not | |
85 | stable, that is, if two members compare as equal, their order in | |
86 | the sorted array is undefined. | |
87 | .Pp | |
88 | The | |
89 | .Fn qsort | |
90 | function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, | |
91 | a variant of partition-exchange sorting; in particular, see D.E. Knuth's | |
92 | Algorithm Q. | |
93 | .Fn Qsort | |
94 | takes O N lg N average time. | |
95 | This implementation uses median selection to avoid the traditional | |
96 | O N**2 worst-case behavior. | |
97 | .Pp | |
98 | The | |
99 | .Fn heapsort | |
100 | function is an implementation of J.W.J. William's ``heapsort'' algorithm, | |
101 | a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. | |
102 | .Fn Heapsort | |
103 | takes O N lg N worst-case time. | |
104 | Its | |
105 | .Em only | |
106 | advantage over | |
107 | .Fn qsort | |
108 | is that it uses no additional memory. | |
109 | .Sh RETURN VALUES | |
110 | The | |
111 | .Fn qsort | |
112 | function | |
113 | returns no value. | |
114 | .Pp | |
115 | Upon successful completion, | |
116 | .Fn heapsort | |
117 | returns 0. | |
118 | Otherwise, it returns \-1 and the global variable | |
119 | .Va errno | |
120 | is set to indicate the error. | |
121 | .Sh ERRORS | |
122 | The | |
123 | .Fn heapsort | |
124 | function succeeds unless: | |
125 | .Bl -tag -width Er | |
126 | .It Bq Er EINVAL | |
127 | The | |
128 | .Fa size | |
129 | argument is zero. | |
130 | .Sh COMPATIBILITY | |
131 | Previous versions of | |
132 | .Fn qsort | |
133 | did not permit the comparison routine to itself call | |
134 | .Fn qsort 3 . | |
135 | This is no longer true. | |
136 | .Sh SEE ALSO | |
137 | .Xr sort 1 , | |
138 | .Xr radixsort 3 | |
139 | .Rs | |
140 | .%A Hoare, C.A.R. | |
141 | .%D 1962 | |
142 | .%T "Quicksort" | |
143 | .%J "The Computer Journal" | |
144 | .%V 5:1 | |
145 | .%P pp. 10-15 | |
146 | .Re | |
147 | .Rs | |
148 | .%A Williams, J.W.J | |
149 | .%D 1964 | |
150 | .%T "Heapsort" | |
151 | .%J "Communications of the ACM" | |
152 | .%V 7:1 | |
153 | .%P pp. 347-348 | |
154 | .Re | |
155 | .Rs | |
156 | .%A Knuth, D.E. | |
157 | .%D 1968 | |
158 | .%B "The Art of Computer Programming" | |
159 | .%V Vol. 3 | |
160 | .%T "Sorting and Searching" | |
161 | .%P pp. 114-123, 145-149 | |
162 | .Re | |
163 | .Sh STANDARDS | |
164 | The | |
165 | .Fn qsort | |
166 | function | |
167 | conforms to | |
168 | .St -ansiC . |