summaryrefslogtreecommitdiff
path: root/src/lib/libc/stdlib/heapsort.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libc/stdlib/heapsort.c')
-rw-r--r--src/lib/libc/stdlib/heapsort.c8
1 files changed, 4 insertions, 4 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