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