From 6f82d0e8f9756938f04071892206a5af85e676f0 Mon Sep 17 00:00:00 2001 From: cvs2svn Date: Fri, 13 Jul 2012 17:49:56 +0000 Subject: This commit was manufactured by cvs2git to create tag 'eric_g2k12'. --- src/lib/libc/stdlib/qsort.3 | 233 -------------------------------------------- 1 file changed, 233 deletions(-) delete mode 100644 src/lib/libc/stdlib/qsort.3 (limited to 'src/lib/libc/stdlib/qsort.3') diff --git a/src/lib/libc/stdlib/qsort.3 b/src/lib/libc/stdlib/qsort.3 deleted file mode 100644 index 92c75d5365..0000000000 --- a/src/lib/libc/stdlib/qsort.3 +++ /dev/null @@ -1,233 +0,0 @@ -.\" Copyright (c) 1990, 1991, 1993 -.\" The Regents of the University of California. All rights reserved. -.\" -.\" This code is derived from software contributed to Berkeley by -.\" the American National Standards Committee X3, on Information -.\" Processing Systems. -.\" -.\" Redistribution and use in source and binary forms, with or without -.\" modification, are permitted provided that the following conditions -.\" are met: -.\" 1. Redistributions of source code must retain the above copyright -.\" notice, this list of conditions and the following disclaimer. -.\" 2. Redistributions in binary form must reproduce the above copyright -.\" notice, this list of conditions and the following disclaimer in the -.\" documentation and/or other materials provided with the distribution. -.\" 3. Neither the name of the University nor the names of its contributors -.\" may be used to endorse or promote products derived from this software -.\" without specific prior written permission. -.\" -.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND -.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE -.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS -.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) -.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT -.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF -.\" SUCH DAMAGE. -.\" -.\" $OpenBSD: qsort.3,v 1.15 2007/05/31 19:19:31 jmc Exp $ -.\" -.Dd $Mdocdate: May 31 2007 $ -.Dt QSORT 3 -.Os -.Sh NAME -.Nm qsort , -.Nm heapsort , -.Nm mergesort -.Nd sort functions -.Sh SYNOPSIS -.Fd #include -.Ft void -.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" -.Ft int -.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" -.Ft int -.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" -.Sh DESCRIPTION -The -.Fn qsort -function is a modified partition-exchange sort, or quicksort. -The -.Fn heapsort -function is a modified selection sort. -The -.Fn mergesort -function is a modified merge sort with exponential search -intended for sorting data with pre-existing order. -.Pp -The -.Fn qsort -and -.Fn heapsort -functions sort an array of -.Fa nmemb -objects, the initial member of which is pointed to by -.Fa base . -The size of each object is specified by -.Fa size . -.Fn mergesort -behaves similarly, but -.Em requires -that -.Fa size -be greater than -.Dq "sizeof(void *) / 2" . -.Pp -The contents of the array -.Fa base -are sorted in ascending order according to -a comparison function pointed to by -.Fa compar , -which requires two arguments pointing to the objects being -compared. -.Pp -The comparison function must return an integer less than, equal to, or -greater than zero if the first argument is considered to be respectively -less than, equal to, or greater than the second. -.Pp -The functions -.Fn qsort -and -.Fn heapsort -are -.Em not -stable, that is, if two members compare as equal, their order in -the sorted array is undefined. -The function -.Fn mergesort -is stable. -.Pp -The -.Fn qsort -function is an implementation of C.A.R. Hoare's -.Dq quicksort -algorithm, -a variant of partition-exchange sorting; in particular, see D.E. Knuth's -Algorithm Q. -.Fn qsort -takes O N lg N average time. -This implementation uses median selection to avoid its -O N**2 worst-case behavior. -.Pp -The -.Fn heapsort -function is an implementation of J.W.J. William's -.Dq heapsort -algorithm, -a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. -.Fn heapsort -takes O N lg N worst-case time. -This implementation of -.Fn heapsort -is implemented without recursive function calls. -.Pp -The function -.Fn mergesort -requires additional memory of size -.Fa nmemb * -.Fa size -bytes; it should be used only when space is not at a premium. -.Fn mergesort -is optimized for data with pre-existing order; its worst case -time is O N lg N; its best case is O N. -.Pp -Normally, -.Fn qsort -is faster than -.Fn mergesort , -which is faster than -.Fn heapsort . -Memory availability and pre-existing order in the data can make this untrue. -.Sh RETURN VALUES -The -.Fn qsort -function returns no value. -.Pp -Upon successful completion, -.Fn heapsort -and -.Fn mergesort -return 0. -Otherwise, they return \-1 and the global variable -.Va errno -is set to indicate the error. -.Sh ERRORS -The -.Fn heapsort -and -.Fn mergesort -functions succeed unless: -.Bl -tag -width Er -.It Bq Er EINVAL -The -.Fa size -argument is zero, or the -.Fa size -argument to -.Fn mergesort -is less than -.Dq "sizeof(void *) / 2" . -.It Bq Er ENOMEM -.Fn heapsort -or -.Fn mergesort -were unable to allocate memory. -.El -.Sh SEE ALSO -.Xr sort 1 , -.Xr radixsort 3 -.Rs -.%A Hoare, C.A.R. -.%D 1962 -.%T "Quicksort" -.%J "The Computer Journal" -.%V 5:1 -.%P pp. 10-15 -.Re -.Rs -.%A Williams, J.W.J -.%D 1964 -.%T "Heapsort" -.%J "Communications of the ACM" -.%V 7:1 -.%P pp. 347\-348 -.Re -.Rs -.%A Knuth, D.E. -.%D 1968 -.%B "The Art of Computer Programming" -.%V Vol. 3 -.%T "Sorting and Searching" -.%P pp. 114\-123, 145\-149 -.Re -.Rs -.%A McIlroy, P.M. -.%T "Optimistic Sorting and Information Theoretic Complexity" -.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" -.%P pp. 467\-464 -.%D January 1993 -.Re -.Rs -.%A Bentley, J.L. -.%A McIlroy, M.D. -.%T "Engineering a Sort Function" -.%J "Software \- Practice and Experience" -.%V Vol. 23(11) -.%P pp. 1249\-1265 -.%D November 1993 -.Re -.Sh STANDARDS -Previous versions of -.Fn qsort -did not permit the comparison routine itself to call -.Fn qsort . -This is no longer true. -.Pp -The -.Fn qsort -function conforms to -.St -ansiC . -- cgit v1.2.3-55-g6feb