stdlib/FreeBSD/qsort.3

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