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.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 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.
 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 ERRORS
 213 The
 214 .Fn heapsort
 215 and
 216 .Fn mergesort
 217 functions succeed unless:
 218 .Bl -tag -width Er
 219 .It Bq Er EINVAL
 220 The
 221 .Fa size
 222 argument is zero, or,
 223 the
 224 .Fa size
 225 argument to
 226 .Fn mergesort
 227 is less than
 228 .Dq "sizeof(void *) / 2" .
 229 .It Bq Er ENOMEM
 230 The
 231 .Fn heapsort
 232 or
 233 .Fn mergesort
 234 functions
 235 were unable to allocate memory.
 236 .El
 237 .Sh COMPATIBILITY
 238 Previous versions of
 239 .Fn qsort
 240 did not permit the comparison routine itself to call
 241 .Fn qsort 3 .
 242 This is no longer true.
 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 .