projects / unix-history / blame
| Commit | Line | Data |
|---|---|---|
| 183abe36 KB |
1 | .\" Copyright (c) 1990 The Regents of the University of California. |
| 2 | .\" All rights reserved. | |
| bfbd68e0 | 3 | .\" |
| 183abe36 KB |
4 | .\" %sccs.include.redist.man% |
| 5 | .\" | |
| 6e0cb3ec | 6 | .\" @(#)qsort.3 6.4 (Berkeley) %G% |
| bfbd68e0 | 7 | .\" |
| dc15bb49 | 8 | .TH QSORT 3 "" |
| bfbd68e0 KM |
9 | .UC 4 |
| 10 | .SH NAME | |
| 11 | qsort \- quicker sort | |
| 12 | .SH SYNOPSIS | |
| 13 | .nf | |
| 183abe36 KB |
14 | .ft B |
| 15 | #include <stdlib.h> | |
| 16 | ||
| 17 | void | |
| 18 | qsort(void *base, size_t nmemb, size_t size, | |
| 6e0cb3ec KB |
19 | .RS |
| 20 | .\" have to reset bold font | |
| 21 | .ft B | |
| 183abe36 | 22 | int (*compar)(const void *, const void *)); |
| 6e0cb3ec | 23 | .RE |
| 183abe36 | 24 | .ft R |
| bfbd68e0 KM |
25 | .fi |
| 26 | .SH DESCRIPTION | |
| 27 | .I Qsort | |
| 6e0cb3ec | 28 | is a modified partition-exchange sort, or quicksort. |
| 183abe36 KB |
29 | .PP |
| 30 | The | |
| 31 | .I qsort | |
| 32 | function sorts an array of | |
| 33 | .I nmemb | |
| 34 | objects, the initial member of which is pointed to by | |
| 35 | .IR base . | |
| 36 | The size of each object is specified by | |
| 37 | .IR size . | |
| 38 | .PP | |
| 39 | The contents of the array are sorted in ascending order according to | |
| 40 | a comparison function pointed to by | |
| 41 | .IR compar , | |
| 42 | which is called with two arguments that point to the objects being | |
| 43 | compared. | |
| 44 | .PP | |
| 45 | The comparison function must return an integer less than, equal to, or | |
| 46 | greater than zero if the first argument is considered to be respectively | |
| bfbd68e0 | 47 | less than, equal to, or greater than the second. |
| 183abe36 | 48 | .PP |
| 6e0cb3ec KB |
49 | .I Qsort |
| 50 | is | |
| 51 | .B not | |
| 52 | stable, that is, if two members compare as equal, their order in | |
| 53 | the sorted array is undefined. | |
| 54 | .PP | |
| 55 | .I Qsort | |
| 56 | is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, a variant | |
| 57 | of partition-exchange sorting; in particular, see D.E. Knuth's Algorithm Q. | |
| 58 | .I Qsort | |
| 59 | takes O N lg N average time. | |
| 60 | .SH "RETURN VALUES" | |
| 61 | .I Qsort | |
| 62 | returns no value. | |
| 63 | .SH COMPATIBILITY | |
| 64 | Previous versions of | |
| 65 | .I qsort | |
| 66 | did not permit the comparison routine to itself call | |
| 67 | .IR qsort (3). | |
| 68 | This is no longer true. | |
| bfbd68e0 | 69 | .SH "SEE ALSO" |
| 6e0cb3ec KB |
70 | sort(1), radixsort(3) |
| 71 | .sp | |
| 72 | Hoare, C.A.R. [1962]. "Quicksort", The Computer Journal, 5:1, pp. 10-15. | |
| 73 | .br | |
| 74 | Knuth, D.E. [1968]. "The Art of Computer Programming Vol. 3: Sorting and | |
| 75 | Searching", pp. 114-123. | |
| 183abe36 | 76 | .SH STANDARDS |
| 6e0cb3ec | 77 | .I Qsort |
| 183abe36 | 78 | conforms to ANSI X3.159-1989 (``ANSI C''). |