stdlib/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 .\" 4. Neither the name of the University nor the names of its contributors
  17 .\"    may be used to endorse or promote products derived from this software
  18 .\"    without specific prior written permission.
  19 .\"
  20 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30 .\" SUCH DAMAGE.
  31 .\"
  32 .\"     @(#)qsort.3     8.1 (Berkeley) 6/4/93
  33 .\" $FreeBSD: src/lib/libc/stdlib/qsort.3,v 1.17 2007/01/09 00:28:10 imp Exp $
  34 .\"
  35 .Dd September 30, 2003
  36 .Dt QSORT 3
  37 .Os
  38 .Sh NAME
  39 .Nm heapsort ,
  40 #ifdef UNIFDEF_BLOCKS
  41 .Nm heapsort_b ,
  42 #endif
  43 .Nm mergesort ,
  44 #ifdef UNIFDEF_BLOCKS
  45 .Nm mergesort_b ,
  46 #endif
  47 .Nm qsort ,
  48 #ifdef UNIFDEF_BLOCKS
  49 .Nm qsort_b ,
  50 #endif
  51 .Nm qsort_r
  52 .Nd sort functions
  53 .Sh SYNOPSIS
  54 .In stdlib.h
  55 .Ft int
  56 .Fo heapsort
  57 .Fa "void *base"
  58 .Fa "size_t nel"
  59 .Fa "size_t width"
  60 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  61 .Fc
  62 #ifdef UNIFDEF_BLOCKS
  63 .Ft int
  64 .Fo heapsort_b
  65 .Fa "void *base"
  66 .Fa "size_t nel"
  67 .Fa "size_t width"
  68 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  69 .Fc
  70 #endif
  71 .Ft int
  72 .Fo mergesort
  73 .Fa "void *base"
  74 .Fa "size_t nel"
  75 .Fa "size_t width"
  76 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  77 .Fc
  78 #ifdef UNIFDEF_BLOCKS
  79 .Ft int
  80 .Fo mergesort_b
  81 .Fa "void *base"
  82 .Fa "size_t nel"
  83 .Fa "size_t width"
  84 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  85 .Fc
  86 #endif
  87 .Ft void
  88 .Fo qsort
  89 .Fa "void *base"
  90 .Fa "size_t nel"
  91 .Fa "size_t width"
  92 .Fa "int \*[lp]*compar\*[rp]\*[lp]const void *, const void *\*[rp]"
  93 .Fc
  94 #ifdef UNIFDEF_BLOCKS
  95 .Ft void
  96 .Fo qsort_b
  97 .Fa "void *base"
  98 .Fa "size_t nel"
  99 .Fa "size_t width"
 100 .Fa "int \*[lp]^compar\*[rp]\*[lp]const void *, const void *\*[rp]"
 101 .Fc
 102 #endif
 103 .Ft void
 104 .Fo qsort_r
 105 .Fa "void *base"
 106 .Fa "size_t nel"
 107 .Fa "size_t width"
 108 .Fa "void *thunk"
 109 .Fa "int \*[lp]*compar\*[rp]\*[lp]void *, const void *, const void *\*[rp]"
 110 .Fc
 111 .Sh DESCRIPTION
 112 The
 113 .Fn qsort
 114 function is a modified partition-exchange sort, or quicksort.
 115 The
 116 .Fn heapsort
 117 function is a modified selection sort.
 118 The
 119 .Fn mergesort
 120 function is a modified merge sort with exponential search,
 121 intended for sorting data with pre-existing order.
 122 .Pp
 123 The
 124 .Fn qsort
 125 and
 126 .Fn heapsort
 127 functions sort an array of
 128 .Fa nel
 129 objects, the initial member of which is pointed to by
 130 .Fa base .
 131 The size of each object is specified by
 132 .Fa width .
 133 The
 134 .Fn mergesort
 135 function
 136 behaves similarly, but
 137 .Em requires
 138 that
 139 .Fa width
 140 be greater than or equal to
 141 .Dq "sizeof(void *) / 2" .
 142 .Pp
 143 The contents of the array
 144 .Fa base
 145 are sorted in ascending order according to
 146 a comparison function pointed to by
 147 .Fa compar ,
 148 which requires two arguments pointing to the objects being
 149 compared.
 150 .Pp
 151 The comparison function must return an integer less than, equal to, or
 152 greater than zero if the first argument is considered to be respectively
 153 less than, equal to, or greater than the second.
 154 .Pp
 155 The
 156 .Fn qsort_r
 157 function behaves identically to
 158 .Fn qsort ,
 159 except that it takes an additional argument,
 160 .Fa thunk ,
 161 which is passed unchanged as the first argument to function pointed to
 162 .Fa compar .
 163 This allows the comparison function to access additional
 164 data without using global variables, and thus
 165 .Fn qsort_r
 166 is suitable for use in functions which must be reentrant.
 167 .Pp
 168 The algorithms implemented by
 169 .Fn qsort ,
 170 .Fn qsort_r ,
 171 and
 172 .Fn heapsort
 173 are
 174 .Em not
 175 stable; that is, if two members compare as equal, their order in
 176 the sorted array is undefined.
 177 The
 178 .Fn mergesort
 179 algorithm is stable.
 180 .Pp
 181 The
 182 .Fn qsort
 183 and
 184 .Fn qsort_r
 185 functions are an implementation of C.A.R.
 186 Hoare's
 187 .Dq quicksort
 188 algorithm,
 189 a variant of partition-exchange sorting; in particular, see
 190 .An D.E. Knuth Ns 's
 191 .%T "Algorithm Q" .
 192 .Sy Quicksort
 193 takes O N lg N average time.
 194 This implementation uses median selection to avoid its
 195 O N**2 worst-case behavior.
 196 .Pp
 197 The
 198 .Fn heapsort
 199 function is an implementation of
 200 .An "J.W.J. William" Ns 's
 201 .Dq heapsort
 202 algorithm,
 203 a variant of selection sorting; in particular, see
 204 .An "D.E. Knuth" Ns 's
 205 .%T "Algorithm H" .
 206 .Sy Heapsort
 207 takes O N lg N worst-case time.
 208 Its
 209 .Em only
 210 advantage over
 211 .Fn qsort
 212 is that it uses almost no additional memory; while
 213 .Fn qsort
 214 does not allocate memory, it is implemented using recursion.
 215 .Pp
 216 The function
 217 .Fn mergesort
 218 requires additional memory of size
 219 .Fa nel *
 220 .Fa width
 221 bytes; it should be used only when space is not at a premium.
 222 The
 223 .Fn mergesort
 224 function
 225 is optimized for data with pre-existing order; its worst case
 226 time is O N lg N; its best case is O N.
 227 .Pp
 228 Normally,
 229 .Fn qsort
 230 is faster than
 231 .Fn mergesort
 232 which is faster than
 233 .Fn heapsort .
 234 Memory availability and pre-existing order in the data can make this
 235 untrue.
 236 #ifdef UNIFDEF_BLOCKS
 237 .Pp
 238 The
 239 .Fn heapsort_b ,
 240 .Fn mergesort_b ,
 241 and
 242 .Fn qsort_b
 243 routines are like the corresponding routines without the _b suffix, expect
 244 that the
 245 .Fa compar
 246 callback is a block pointer instead of a function pointer.
 247 #endif
 248 .Sh RETURN VALUES
 249 The
 250 #ifdef UNIFDEF_BLOCKS
 251 .Fn qsort ,
 252 .Fn qsort_b
 253 #else
 254 .Fn qsort
 255 #endif
 256 and
 257 .Fn qsort_r
 258 functions
 259 return no value.
 260 .Pp
 261 #ifdef UNIFDEF_BLOCKS
 262 .ds HEAPSORT_B heapsort_b
 263 .ds MERGESORT_B mergesort_b
 264 #endif
 265 .Rv -std heapsort \*[HEAPSORT_B] mergesort \*[MERGESORT_B]
 266 .Sh COMPATIBILITY
 267 Previous versions of
 268 .Fn qsort
 269 did not permit the comparison routine itself to call
 270 .Fn qsort 3 .
 271 This is no longer true.
 272 .Sh ERRORS
 273 The
 274 #ifdef UNIFDEF_BLOCKS
 275 .Fn heapsort ,
 276 .Fn heapsort_b ,
 277 .Fn mergesort ,
 278 and
 279 .Fn mergesort_b
 280 #else
 281 .Fn heapsort
 282 and
 283 .Fn mergesort
 284 #endif
 285 functions succeed unless:
 286 .Bl -tag -width Er
 287 .It Bq Er EINVAL
 288 The
 289 .Fa width
 290 argument is zero, or,
 291 the
 292 .Fa width
 293 argument to
 294 .Fn mergesort
 295 #ifdef UNIFDEF_BLOCKS
 296 or
 297 .Fn mergesort_b
 298 #endif
 299 is less than
 300 .Dq "sizeof(void *) / 2" .
 301 .It Bq Er ENOMEM
 302 The
 303 #ifdef UNIFDEF_BLOCKS
 304 .Fn heapsort ,
 305 .Fn heapsort_b ,
 306 .Fn mergesort ,
 307 or
 308 .Fn mergesort_b
 309 #else
 310 .Fn heapsort
 311 or
 312 .Fn mergesort
 313 #endif
 314 functions
 315 were unable to allocate memory.
 316 .El
 317 .Sh SEE ALSO
 318 .Xr sort 1 ,
 319 .Xr radixsort 3
 320 .Rs
 321 .%A Hoare, C.A.R.
 322 .%D 1962
 323 .%T "Quicksort"
 324 .%J "The Computer Journal"
 325 .%V 5:1
 326 .%P pp. 10-15
 327 .Re
 328 .Rs
 329 .%A Williams, J.W.J
 330 .%D 1964
 331 .%T "Heapsort"
 332 .%J "Communications of the ACM"
 333 .%V 7:1
 334 .%P pp. 347-348
 335 .Re
 336 .Rs
 337 .%A Knuth, D.E.
 338 .%D 1968
 339 .%B "The Art of Computer Programming"
 340 .%V Vol. 3
 341 .%T "Sorting and Searching"
 342 .%P pp. 114-123, 145-149
 343 .Re
 344 .Rs
 345 .%A McIlroy, P.M.
 346 .%T "Optimistic Sorting and Information Theoretic Complexity"
 347 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 348 .%V January 1992
 349 .Re
 350 .Rs
 351 .%A Bentley, J.L.
 352 .%A McIlroy, M.D.
 353 .%T "Engineering a Sort Function"
 354 .%J "Software--Practice and Experience"
 355 .%V Vol. 23(11)
 356 .%P pp. 1249-1265
 357 .%D November\ 1993
 358 .Re
 359 .Sh STANDARDS
 360 The
 361 .Fn qsort
 362 function
 363 conforms to
 364 .St -isoC .