lib/libc/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. 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 .\" $DragonFly: src/lib/libc/stdlib/qsort.3,v 1.4 2006/02/17 19:35:06 swildner Exp $
  35 .\"
  36 .Dd September 30, 2003
  37 .Dt QSORT 3
  38 .Os
  39 .Sh NAME
  40 .Nm qsort ,
  41 .Nm qsort_r ,
  42 .Nm heapsort ,
  43 .Nm 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 (*compar)(const void *, const void *)"
  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 (*compar)(void *, const void *, const void *)"
  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 (*compar)(const void *, const void *)"
  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 (*compar)(const void *, const void *)"
  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.
 153 Hoare's
 154 .Dq quicksort
 155 algorithm,
 156 a variant of partition-exchange sorting; in particular, see
 157 .An D.E. Knuth Ns 's
 158 .%T "Algorithm Q" .
 159 .Sy Quicksort
 160 takes O N lg N average time.
 161 This implementation uses median selection to avoid its
 162 O N**2 worst-case behavior.
 163 .Pp
 164 The
 165 .Fn heapsort
 166 function is an implementation of
 167 .An "J.W.J. William" Ns 's
 168 .Dq heapsort
 169 algorithm,
 170 a variant of selection sorting; in particular, see
 171 .An "D.E. Knuth" Ns 's
 172 .%T "Algorithm H" .
 173 .Sy Heapsort
 174 takes O N lg N worst-case time.
 175 Its
 176 .Em only
 177 advantage over
 178 .Fn qsort
 179 is that it uses almost no additional memory; while
 180 .Fn qsort
 181 does not allocate memory, it is implemented using recursion.
 182 .Pp
 183 The function
 184 .Fn mergesort
 185 requires additional memory of size
 186 .Fa nmemb *
 187 .Fa size
 188 bytes; it should be used only when space is not at a premium.
 189 The
 190 .Fn mergesort
 191 function
 192 is optimized for data with pre-existing order; its worst case
 193 time is O N lg N; its best case is O N.
 194 .Pp
 195 Normally,
 196 .Fn qsort
 197 is faster than
 198 .Fn mergesort
 199 is faster than
 200 .Fn heapsort .
 201 Memory availability and pre-existing order in the data can make this
 202 untrue.
 203 .Sh RETURN VALUES
 204 The
 205 .Fn qsort
 206 and
 207 .Fn qsort_r
 208 functions
 209 return no value.
 210 .Pp
 211 .Rv -std heapsort mergesort
 212 .Sh COMPATIBILITY
 213 Previous versions of
 214 .Fn qsort
 215 did not permit the comparison routine itself to call
 216 .Fn qsort 3 .
 217 This is no longer true.
 218 .Sh ERRORS
 219 The
 220 .Fn heapsort
 221 and
 222 .Fn mergesort
 223 functions succeed unless:
 224 .Bl -tag -width Er
 225 .It Bq Er EINVAL
 226 The
 227 .Fa size
 228 argument is zero, or,
 229 the
 230 .Fa size
 231 argument to
 232 .Fn mergesort
 233 is less than
 234 .Dq "sizeof(void *) / 2" .
 235 .It Bq Er ENOMEM
 236 The
 237 .Fn heapsort
 238 or
 239 .Fn mergesort
 240 functions
 241 were unable to allocate memory.
 242 .El
 243 .Sh SEE ALSO
 244 .Xr sort 1 ,
 245 .Xr radixsort 3
 246 .Rs
 247 .%A Hoare, C.A.R.
 248 .%D 1962
 249 .%T "Quicksort"
 250 .%J "The Computer Journal"
 251 .%V 5:1
 252 .%P pp. 10-15
 253 .Re
 254 .Rs
 255 .%A Williams, J.W.J
 256 .%D 1964
 257 .%T "Heapsort"
 258 .%J "Communications of the ACM"
 259 .%V 7:1
 260 .%P pp. 347-348
 261 .Re
 262 .Rs
 263 .%A Knuth, D.E.
 264 .%D 1968
 265 .%B "The Art of Computer Programming"
 266 .%V Vol. 3
 267 .%T "Sorting and Searching"
 268 .%P pp. 114-123, 145-149
 269 .Re
 270 .Rs
 271 .%A McIlroy, P.M.
 272 .%T "Optimistic Sorting and Information Theoretic Complexity"
 273 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 274 .%V January 1992
 275 .Re
 276 .Rs
 277 .%A Bentley, J.L.
 278 .%A McIlroy, M.D.
 279 .%T "Engineering a Sort Function"
 280 .%J "Software--Practice and Experience"
 281 .%V Vol. 23(11)
 282 .%P pp. 1249-1265
 283 .%D November\ 1993
 284 .Re
 285 .Sh STANDARDS
 286 The
 287 .Fn qsort
 288 function
 289 conforms to
 290 .St -isoC .