Commit | Line | Data |
---|---|---|
ae59e04c | 1 | .\" Copyright (c) 1990, 1991 The Regents of the University of California. |
183abe36 | 2 | .\" All rights reserved. |
bfbd68e0 | 3 | .\" |
043368e6 KB |
4 | .\" This code is derived from software contributed to Berkeley by |
5 | .\" the American National Standards Committee X3, on Information | |
6 | .\" Processing Systems. | |
7 | .\" | |
183abe36 KB |
8 | .\" %sccs.include.redist.man% |
9 | .\" | |
043368e6 | 10 | .\" @(#)qsort.3 6.7 (Berkeley) %G% |
bfbd68e0 | 11 | .\" |
ae59e04c CL |
12 | .Dd |
13 | .Dt QSORT 3 | |
14 | .Os | |
15 | .Sh NAME | |
07e43f16 KB |
16 | .Nm qsort, heapsort |
17 | .Nd sort functions | |
ae59e04c CL |
18 | .Sh SYNOPSIS |
19 | .Fd #include <stdlib.h> | |
20 | .Ft void | |
21 | .Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" | |
07e43f16 KB |
22 | .Ft int |
23 | .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" | |
ae59e04c CL |
24 | .Sh DESCRIPTION |
25 | The | |
26 | .Fn qsort | |
07e43f16 KB |
27 | function is a modified partition-exchange sort, or quicksort. |
28 | The | |
29 | .Fn heapsort | |
30 | function is a modified selection sort. | |
ae59e04c | 31 | .Pp |
183abe36 | 32 | The |
ae59e04c | 33 | .Fn qsort |
07e43f16 KB |
34 | and |
35 | .Fn heapsort | |
36 | functions sort an array of | |
ae59e04c | 37 | .Fa nmemb |
183abe36 | 38 | objects, the initial member of which is pointed to by |
ae59e04c | 39 | .Fa base . |
183abe36 | 40 | The size of each object is specified by |
ae59e04c CL |
41 | .Fa size . |
42 | .Pp | |
183abe36 KB |
43 | The contents of the array are sorted in ascending order according to |
44 | a comparison function pointed to by | |
ae59e04c | 45 | .Fa compar , |
183abe36 KB |
46 | which is called with two arguments that point to the objects being |
47 | compared. | |
ae59e04c | 48 | .Pp |
183abe36 KB |
49 | The comparison function must return an integer less than, equal to, or |
50 | greater than zero if the first argument is considered to be respectively | |
bfbd68e0 | 51 | less than, equal to, or greater than the second. |
ae59e04c | 52 | .Pp |
07e43f16 | 53 | The functions |
ae59e04c | 54 | .Fn qsort |
07e43f16 KB |
55 | and |
56 | .Fn heapsort | |
57 | are | |
ae59e04c | 58 | .Em not |
6e0cb3ec KB |
59 | stable, that is, if two members compare as equal, their order in |
60 | the sorted array is undefined. | |
ae59e04c CL |
61 | .Pp |
62 | The | |
63 | .Fn qsort | |
07e43f16 KB |
64 | function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, |
65 | a variant of partition-exchange sorting; in particular, see D.E. Knuth's | |
66 | Algorithm Q. | |
ae59e04c | 67 | .Fn Qsort |
6e0cb3ec | 68 | takes O N lg N average time. |
07e43f16 KB |
69 | This implementation uses median selection to avoid the traditional |
70 | O N**2 worst-case behavior. | |
71 | .Pp | |
72 | The | |
73 | .Fn heapsort | |
74 | function is an implementation of J.W.J. William's ``heapsort'' algorithm, | |
75 | a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. | |
76 | .Fn Heapsort | |
77 | takes O N lg N worst-case time. | |
78 | Its | |
79 | .Em only | |
80 | advantage over | |
81 | .Fn qsort | |
82 | is that it uses no additional memory. | |
ae59e04c CL |
83 | .Sh RETURN VALUES |
84 | The | |
85 | .Fn qsort | |
86 | function | |
6e0cb3ec | 87 | returns no value. |
07e43f16 KB |
88 | .Pp |
89 | Upon successful completion, | |
90 | .Fn heapsort | |
91 | returns 0. | |
92 | Otherwise, it returns \-1 and the global variable | |
93 | .Va errno | |
94 | is set to indicate the error. | |
95 | .Sh ERRORS | |
96 | The | |
97 | .Fn heapsort | |
98 | function succeeds unless: | |
99 | .Bl -tag -width Er | |
100 | .It Bq Er EINVAL | |
101 | The | |
102 | .Fa size | |
103 | argument is zero. | |
ae59e04c | 104 | .Sh COMPATIBILITY |
6e0cb3ec | 105 | Previous versions of |
ae59e04c | 106 | .Fn qsort |
6e0cb3ec | 107 | did not permit the comparison routine to itself call |
ae59e04c | 108 | .Fn qsort 3 . |
6e0cb3ec | 109 | This is no longer true. |
ae59e04c CL |
110 | .Sh SEE ALSO |
111 | .Xr sort 1 , | |
112 | .Xr radixsort 3 | |
113 | .Rs | |
114 | .%A Hoare, C.A.R. | |
115 | .%D 1962 | |
116 | .%T "Quicksort" | |
117 | .%J "The Computer Journal" | |
118 | .%V 5:1 | |
119 | .%P pp. 10-15 | |
120 | .Re | |
121 | .Rs | |
07e43f16 KB |
122 | .%A Williams, J.W.J |
123 | .%D 1964 | |
124 | .%T "Heapsort" | |
125 | .%J "Communications of the ACM" | |
126 | .%V 7:1 | |
127 | .%P pp. 347-348 | |
128 | .Re | |
129 | .Rs | |
ae59e04c CL |
130 | .%A Knuth, D.E. |
131 | .%D 1968 | |
132 | .%B "The Art of Computer Programming" | |
133 | .%V Vol. 3 | |
134 | .%T "Sorting and Searching" | |
07e43f16 | 135 | .%P pp. 114-123, 145-149 |
ae59e04c CL |
136 | .Re |
137 | .Sh STANDARDS | |
138 | The | |
139 | .Fn qsort | |
140 | function | |
141 | conforms to | |
142 | .St -ansiC . |