summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjmc <>2003-09-07 18:57:05 +0000
committerjmc <>2003-09-07 18:57:05 +0000
commita6347b2b07d039d01a04b22538220a7c6d7697b3 (patch)
treef3551dfa024cd6e67ad8b3e50aa45f06a4654040
parent6fc3be9c670852e899a4e265db78f218c4150b50 (diff)
downloadopenbsd-a6347b2b07d039d01a04b22538220a7c6d7697b3.tar.gz
openbsd-a6347b2b07d039d01a04b22538220a7c6d7697b3.tar.bz2
openbsd-a6347b2b07d039d01a04b22538220a7c6d7697b3.zip
typos from Brian Poole;
ok deraadt@
-rw-r--r--src/lib/libc/stdlib/heapsort.c8
-rw-r--r--src/lib/libc/stdlib/qsort.34
2 files changed, 6 insertions, 6 deletions
diff --git a/src/lib/libc/stdlib/heapsort.c b/src/lib/libc/stdlib/heapsort.c
index 604aa37d4d..e8f090524f 100644
--- a/src/lib/libc/stdlib/heapsort.c
+++ b/src/lib/libc/stdlib/heapsort.c
@@ -31,7 +31,7 @@
31 */ 31 */
32 32
33#if defined(LIBC_SCCS) && !defined(lint) 33#if defined(LIBC_SCCS) && !defined(lint)
34static char *rcsid = "$OpenBSD: heapsort.c,v 1.4 2003/06/02 20:18:37 millert Exp $"; 34static char *rcsid = "$OpenBSD: heapsort.c,v 1.5 2003/09/07 18:57:05 jmc Exp $";
35#endif /* LIBC_SCCS and not lint */ 35#endif /* LIBC_SCCS and not lint */
36 36
37#include <sys/types.h> 37#include <sys/types.h>
@@ -68,7 +68,7 @@ static char *rcsid = "$OpenBSD: heapsort.c,v 1.4 2003/06/02 20:18:37 millert Exp
68 * Build the list into a heap, where a heap is defined such that for 68 * Build the list into a heap, where a heap is defined such that for
69 * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N. 69 * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
70 * 70 *
71 * There two cases. If j == nmemb, select largest of Ki and Kj. If 71 * There are two cases. If j == nmemb, select largest of Ki and Kj. If
72 * j < nmemb, select largest of Ki, Kj and Kj+1. 72 * j < nmemb, select largest of Ki, Kj and Kj+1.
73 */ 73 */
74#define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) { \ 74#define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) { \
@@ -90,12 +90,12 @@ static char *rcsid = "$OpenBSD: heapsort.c,v 1.4 2003/06/02 20:18:37 millert Exp
90 * Select the top of the heap and 'heapify'. Since by far the most expensive 90 * Select the top of the heap and 'heapify'. Since by far the most expensive
91 * action is the call to the compar function, a considerable optimization 91 * action is the call to the compar function, a considerable optimization
92 * in the average case can be achieved due to the fact that k, the displaced 92 * in the average case can be achieved due to the fact that k, the displaced
93 * elememt, is ususally quite small, so it would be preferable to first 93 * elememt, is usually quite small, so it would be preferable to first
94 * heapify, always maintaining the invariant that the larger child is copied 94 * heapify, always maintaining the invariant that the larger child is copied
95 * over its parent's record. 95 * over its parent's record.
96 * 96 *
97 * Then, starting from the *bottom* of the heap, finding k's correct place, 97 * Then, starting from the *bottom* of the heap, finding k's correct place,
98 * again maintianing the invariant. As a result of the invariant no element 98 * again maintaining the invariant. As a result of the invariant no element
99 * is 'lost' when k is assigned its correct place in the heap. 99 * is 'lost' when k is assigned its correct place in the heap.
100 * 100 *
101 * The time savings from this optimization are on the order of 15-20% for the 101 * The time savings from this optimization are on the order of 15-20% for the
diff --git a/src/lib/libc/stdlib/qsort.3 b/src/lib/libc/stdlib/qsort.3
index 2921cbbe69..0af8606773 100644
--- a/src/lib/libc/stdlib/qsort.3
+++ b/src/lib/libc/stdlib/qsort.3
@@ -29,7 +29,7 @@
29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30.\" SUCH DAMAGE. 30.\" SUCH DAMAGE.
31.\" 31.\"
32.\" $OpenBSD: qsort.3,v 1.12 2003/06/02 20:18:38 millert Exp $ 32.\" $OpenBSD: qsort.3,v 1.13 2003/09/07 18:57:05 jmc Exp $
33.\" 33.\"
34.Dd June 4, 1993 34.Dd June 4, 1993
35.Dt QSORT 3 35.Dt QSORT 3
@@ -122,7 +122,7 @@ a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H.
122.Fn heapsort 122.Fn heapsort
123takes O N lg N worst-case time. 123takes O N lg N worst-case time.
124This implementation of 124This implementation of
125.Fn qsort 125.Fn heapsort
126is implemented without recursive function calls. 126is implemented without recursive function calls.
127.Pp 127.Pp
128The function 128The function