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