From eb8dd9dca1228af0cd132f515509051ecfabf6f6 Mon Sep 17 00:00:00 2001 From: cvs2svn Date: Mon, 14 Apr 2025 17:32:06 +0000 Subject: This commit was manufactured by cvs2git to create tag 'tb_20250414'. --- src/lib/libc/stdlib/qsort.3 | 276 -------------------------------------------- 1 file changed, 276 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 4c0cddaccb..0000000000 --- a/src/lib/libc/stdlib/qsort.3 +++ /dev/null @@ -1,276 +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.27 2020/02/08 01:09:57 jsg Exp $ -.\" -.Dd $Mdocdate: February 8 2020 $ -.Dt QSORT 3 -.Os -.Sh NAME -.Nm qsort , -.Nm heapsort , -.Nm mergesort -.Nd sort functions -.Sh SYNOPSIS -.In stdlib.h -.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 int 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 and will fall back to -.Fn heapsort -if the recursion depth exceeds 2 lg N. -.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 -.Rv -std heapsort mergesort -.Sh EXAMPLES -.Bd -literal -#include -#include -#include - -char *array[] = { "XX", "YYY", "Z" }; -#define N (sizeof(array) / sizeof(array[0])) - -int -cmp(const void *a, const void *b) -{ - /* - * a and b point to elements of the array. - * Cast and dereference to obtain the actual elements, - * which are also pointers in this case. - */ - size_t lena = strlen(*(const char **)a); - size_t lenb = strlen(*(const char **)b); - /* - * Do not subtract the lengths. The difference between values - * cannot be represented by an int. - */ - return lena < lenb ? -1 : lena > lenb; -} - -int -main() -{ - size_t i; - - qsort(array, N, sizeof(array[0]), cmp); - for (i = 0; i < N; i++) - printf("%s\en", array[i]); -} -.Ed -.Pp -It is almost always an error to use subtraction to compute the return value -of the comparison function. -.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 -.Rs -.%A Musser, D. -.%T "Introspective Sorting and Selection Algorithms" -.%J "Software \- Practice and Experience" -.%V Vol. 27(8) -.%P pp. 983\-993 -.%D August 1997 -.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 . -.Sh HISTORY -A -.Fn qsort -function first appeared in -.At v2 . -- cgit v1.2.3-55-g6feb