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