| qsort.3 (8aefde060768b2636e1e9a842692cec605960985) | qsort.3 (eca67d510483ad9565b7b816e16fc72ebe3b2864) |
|---|---|
| 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 --- 22 unchanged lines hidden (view full) --- 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$ 38.\" | 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 --- 22 unchanged lines hidden (view full) --- 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$ 38.\" |
| 39.Dd June 4, 1993 | 39.Dd September 7, 2002 |
| 40.Dt QSORT 3 41.Os 42.Sh NAME | 40.Dt QSORT 3 41.Os 42.Sh NAME |
| 43.Nm qsort , heapsort , mergesort | 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.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" | 44.Nd sort functions 45.Sh LIBRARY 46.Lb libc 47.Sh SYNOPSIS 48.In stdlib.h 49.Ft void 50.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" |
| 51.Ft void 52.Fo qsort_r 53.Fa "void *base" 54.Fa "size_t nmemb" 55.Fa "size_t size" 56.Fa "void *thunk" 57.Fa "int (*compar)(void *, const void *, const void *)" 58.Fc |
|
| 51.Ft int 52.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 53.Ft int 54.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 55.Sh DESCRIPTION 56The 57.Fn qsort 58function is a modified partition-exchange sort, or quicksort. --- 30 unchanged lines hidden (view full) --- 89.Fa compar , 90which requires two arguments pointing to the objects being 91compared. 92.Pp 93The comparison function must return an integer less than, equal to, or 94greater than zero if the first argument is considered to be respectively 95less than, equal to, or greater than the second. 96.Pp | 59.Ft int 60.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 61.Ft int 62.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" 63.Sh DESCRIPTION 64The 65.Fn qsort 66function is a modified partition-exchange sort, or quicksort. --- 30 unchanged lines hidden (view full) --- 97.Fa compar , 98which requires two arguments pointing to the objects being 99compared. 100.Pp 101The comparison function must return an integer less than, equal to, or 102greater than zero if the first argument is considered to be respectively 103less than, equal to, or greater than the second. 104.Pp |
| 97The functions 98.Fn qsort | 105The 106.Fn qsort_r 107function behaves identically to 108.Fn qsort , 109except that it takes an additional argument, 110.Fa thunk , 111which is passed unchanged as the first argument to function pointed to 112.Fa compar . 113This allows the comparison function to access additional 114data without using global variables, and thus 115.Fn qsort_r 116is suitable for use in functions which must be reentrant. 117.Pp 118The algorithms implemented by 119.Fn qsort , 120.Fn qsort_r , |
| 99and 100.Fn heapsort 101are 102.Em not 103stable, that is, if two members compare as equal, their order in 104the sorted array is undefined. | 121and 122.Fn heapsort 123are 124.Em not 125stable, that is, if two members compare as equal, their order in 126the sorted array is undefined. |
| 105The function | 127The |
| 106.Fn mergesort | 128.Fn mergesort |
| 107is stable. | 129algorithm is stable. |
| 108.Pp 109The 110.Fn qsort | 130.Pp 131The 132.Fn qsort |
| 111function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, | 133and 134.Fn qsort_r 135functions are an implementation of C.A.R. Hoare's ``quicksort'' algorithm, |
| 112a variant of partition-exchange sorting; in particular, see D.E. Knuth's 113Algorithm Q. | 136a variant of partition-exchange sorting; in particular, see D.E. Knuth's 137Algorithm Q. |
| 114.Fn Qsort | 138.Sy Quicksort |
| 115takes O N lg N average time. 116This implementation uses median selection to avoid its 117O N**2 worst-case behavior. 118.Pp 119The 120.Fn heapsort 121function is an implementation of J.W.J. William's ``heapsort'' algorithm, 122a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. | 139takes O N lg N average time. 140This implementation uses median selection to avoid its 141O N**2 worst-case behavior. 142.Pp 143The 144.Fn heapsort 145function is an implementation of J.W.J. William's ``heapsort'' algorithm, 146a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. |
| 123.Fn Heapsort | 147.Sy Heapsort |
| 124takes O N lg N worst-case time. 125Its 126.Em only 127advantage over 128.Fn qsort 129is that it uses almost no additional memory; while 130.Fn qsort 131does not allocate memory, it is implemented using recursion. --- 14 unchanged lines hidden (view full) --- 146.Fn mergesort 147is faster than 148.Fn heapsort . 149Memory availability and pre-existing order in the data can make this 150untrue. 151.Sh RETURN VALUES 152The 153.Fn qsort | 148takes O N lg N worst-case time. 149Its 150.Em only 151advantage over 152.Fn qsort 153is that it uses almost no additional memory; while 154.Fn qsort 155does not allocate memory, it is implemented using recursion. --- 14 unchanged lines hidden (view full) --- 170.Fn mergesort 171is faster than 172.Fn heapsort . 173Memory availability and pre-existing order in the data can make this 174untrue. 175.Sh RETURN VALUES 176The 177.Fn qsort |
| 154function 155returns no value. | 178and 179.Fn qsort_r 180functions 181return no value. |
| 156.Pp 157.Rv -std heapsort mergesort 158.Sh ERRORS 159The 160.Fn heapsort 161and 162.Fn mergesort 163functions succeed unless: --- 68 unchanged lines hidden --- | 182.Pp 183.Rv -std heapsort mergesort 184.Sh ERRORS 185The 186.Fn heapsort 187and 188.Fn mergesort 189functions succeed unless: --- 68 unchanged lines hidden --- |