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. 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.4.2.5 2001/12/14 18:33:58 ru Exp $
  38 .\" $DragonFly: src/lib/libc/stdlib/qsort.3,v 1.4 2006/02/17 19:35:06 swildner Exp $
  39 .\"
  40 .Dd June 4, 1993
  41 .Dt QSORT 3
  42 .Os
  43 .Sh NAME
  44 .Nm qsort ,
  45 .Nm heapsort ,
  46 .Nm mergesort
  47 .Nd sort functions
  48 .Sh LIBRARY
  49 .Lb libc
  50 .Sh SYNOPSIS
  51 .In stdlib.h
  52 .Ft void
  53 .Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  54 .Ft int
  55 .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  56 .Ft int
  57 .Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
  58 .Sh DESCRIPTION
  59 The
  60 .Fn qsort
  61 function is a modified partition-exchange sort, or quicksort.
  62 The
  63 .Fn heapsort
  64 function is a modified selection sort.
  65 The
  66 .Fn mergesort
  67 function is a modified merge sort with exponential search
  68 intended for sorting data with pre-existing order.
  69 .Pp
  70 The
  71 .Fn qsort
  72 and
  73 .Fn heapsort
  74 functions sort an array of
  75 .Fa nmemb
  76 objects, the initial member of which is pointed to by
  77 .Fa base .
  78 The size of each object is specified by
  79 .Fa size .
  80 .Fn Mergesort
  81 behaves similarly, but
  82 .Em requires
  83 that
  84 .Fa size
  85 be greater than
  86 .Dq "sizeof(void *) / 2" .
  87 .Pp
  88 The contents of the array
  89 .Fa base
  90 are sorted in ascending order according to
  91 a comparison function pointed to by
  92 .Fa compar ,
  93 which requires two arguments pointing to the objects being
  94 compared.
  95 .Pp
  96 The comparison function must return an integer less than, equal to, or
  97 greater than zero if the first argument is considered to be respectively
  98 less than, equal to, or greater than the second.
  99 .Pp
 100 The functions
 101 .Fn qsort
 102 and
 103 .Fn heapsort
 104 are
 105 .Em not
 106 stable, that is, if two members compare as equal, their order in
 107 the sorted array is undefined.
 108 The function
 109 .Fn mergesort
 110 is stable.
 111 .Pp
 112 The
 113 .Fn qsort
 114 function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
 115 a variant of partition-exchange sorting; in particular, see D.E. Knuth's
 116 Algorithm Q.
 117 .Fn Qsort
 118 takes O N lg N average time.
 119 This implementation uses median selection to avoid its
 120 O N**2 worst-case behavior.
 121 .Pp
 122 The
 123 .Fn heapsort
 124 function is an implementation of J.W.J. William's ``heapsort'' algorithm,
 125 a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
 126 .Fn Heapsort
 127 takes O N lg N worst-case time.
 128 Its
 129 .Em only
 130 advantage over
 131 .Fn qsort
 132 is that it uses almost no additional memory; while
 133 .Fn qsort
 134 does not allocate memory, it is implemented using recursion.
 135 .Pp
 136 The function
 137 .Fn mergesort
 138 requires additional memory of size
 139 .Fa nmemb *
 140 .Fa size
 141 bytes; it should be used only when space is not at a premium.
 142 .Fn Mergesort
 143 is optimized for data with pre-existing order; its worst case
 144 time is O N lg N; its best case is O N.
 145 .Pp
 146 Normally,
 147 .Fn qsort
 148 is faster than
 149 .Fn mergesort
 150 is faster than
 151 .Fn heapsort .
 152 Memory availability and pre-existing order in the data can make this
 153 untrue.
 154 .Sh RETURN VALUES
 155 The
 156 .Fn qsort
 157 function
 158 returns no value.
 159 .Pp
 160 .Rv -std heapsort mergesort
 161 .Sh COMPATIBILITY
 162 Previous versions of
 163 .Fn qsort
 164 did not permit the comparison routine itself to call
 165 .Fn qsort 3 .
 166 This is no longer true.
 167 .Sh ERRORS
 168 The
 169 .Fn heapsort
 170 and
 171 .Fn mergesort
 172 functions succeed unless:
 173 .Bl -tag -width Er
 174 .It Bq Er EINVAL
 175 The
 176 .Fa size
 177 argument is zero, or,
 178 the
 179 .Fa size
 180 argument to
 181 .Fn mergesort
 182 is less than
 183 .Dq "sizeof(void *) / 2" .
 184 .It Bq Er ENOMEM
 185 .Fn Heapsort
 186 or
 187 .Fn mergesort
 188 were unable to allocate memory.
 189 .El
 190 .Sh SEE ALSO
 191 .Xr sort 1 ,
 192 .Xr radixsort 3
 193 .Rs
 194 .%A Hoare, C.A.R.
 195 .%D 1962
 196 .%T "Quicksort"
 197 .%J "The Computer Journal"
 198 .%V 5:1
 199 .%P pp. 10-15
 200 .Re
 201 .Rs
 202 .%A Williams, J.W.J
 203 .%D 1964
 204 .%T "Heapsort"
 205 .%J "Communications of the ACM"
 206 .%V 7:1
 207 .%P pp. 347-348
 208 .Re
 209 .Rs
 210 .%A Knuth, D.E.
 211 .%D 1968
 212 .%B "The Art of Computer Programming"
 213 .%V Vol. 3
 214 .%T "Sorting and Searching"
 215 .%P pp. 114-123, 145-149
 216 .Re
 217 .Rs
 218 .%A Mcilroy, P.M.
 219 .%T "Optimistic Sorting and Information Theoretic Complexity"
 220 .%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms"
 221 .%V January 1992
 222 .Re
 223 .Rs
 224 .%A Bentley, J.L.
 225 .%T "Engineering a Sort Function"
 226 .%J "bentley@research.att.com"
 227 .%V January 1992
 228 .Re
 229 .Sh STANDARDS
 230 The
 231 .Fn qsort
 232 function
 233 conforms to
 234 .St -isoC .