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