Category : C Source Code
Archive   : BFSORTS.ZIP
Filename : HSORT.C

 
Output of file : HSORT.C contained in archive : BFSORTS.ZIP
/***********************************************************************/
/* SORT(): Non-Recursive Heap Sort function. */
/* See the function declaration for calling information. */
/* Function is by Bruce Feist; please contact me on CompuServe with */
/* a message on BPROGB, MACDEV, or EASYPLEX if you have any */
/* questions or problems. */
/* You can also reach me at the Enlightened Board, at (703) 370-9528, */
/* N/8/1 */
/* Feel free to make use of this code in your own programs. */
/***********************************************************************/

#define VERBOSE (0)

#include
#include
#include
#include
#include
#include

#include "sort.h"

static void build_heap (void), extract_heap (void);
static void heapify (int, int);

static void show_node (int);
#if VERBOSE
static void show_heap (void);
#endif

/* heapsort uses an array of pointers as its data structure to */
/* represent the heap. */
/* Children of slot i are slots 2i+1 and 2i+2. */

/* Note: as an alternative, we could have made the input array */
/* into a heap (instead of messing with the pointers. */

static char *base, *temp_record;
static int nelem, width, (*compare)(void *, void *);

int
hsort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())

{
base = pbase;
nelem = pnelem;
width = pwidth;
compare = pcompare;
if ((temp_record = malloc (pwidth)) == NULL)
return S_NOMEM;

#if VERBOSE
printf ("Sort (base = %p, n = %u, w = %u)\n", base, nelem, width);
#endif

build_heap ();
extract_heap ();

free (temp_record);

return S_OK;
} /* end hsort */


void
build_heap()

{
register int left;
register char *left_ptr;
int right;

#if VERBOSE
puts ("Building heap. . .\n");
#endif

right = nelem - 1;
for (left = (nelem >> 1) - 1, left_ptr = base + width * left;
1; /* keep going until the 'break' */
left--, left_ptr -= width)
{
#if VERBOSE
printf ("temp <- %d to start heapification.\n", left);
#endif
memcpy (temp_record, left_ptr, width);
heapify (left, right);
if (! left)
break;
}

} /* end build_heap */


void
extract_heap ()
{
register int right;
register char *right_ptr;

#if VERBOSE
puts ("Extracting from heap. . .\n");
#endif

for (right = nelem - 1, right_ptr = base + width * right;
1; /* continue until the 'break' */
right_ptr -= width)
{
memcpy (temp_record, right_ptr, width);
memcpy (right_ptr, base, width);
#if VERBOSE
printf ("temp <- %d to start extract\n", right);
printf ("%d <- %d to start extract\n", right, 0);
printf ("Returning %lf\n", ((double *) base) [right]);
#endif
if (! --right)
break;
heapify (0, right);
}
#if VERBOSE
printf ("%d <- temp to finish extract\n", 0);
#endif
memcpy (base, temp_record, width);
} /* end extract_heap */


/* When heapify is called, (left+1,right) is already heapified and */
/* temp_record contains what we'd like to add to it to make (left,right) */
/* a heap. */
/* So, we look for the first descendent of 'left' that's bigger than */
/* it. All of its ancestors move up a generation, and temp_record */
/* becomes its parent. */

void
heapify (int left, int right)

{
register int child;
register char *ptr_child;
char *ptr_child2, *ptr_parent;

child = left;
ptr_child = base + child * width;

#if VERBOSE
show_heap();
printf ("Heapifying from %d to %d.\n", left, right);
#endif

while (1) /* continue until the 'break' */
{
child <<= 1;
child++;
ptr_parent = ptr_child;

if (child > right) /* if parent was a leaf, replace with temp_record */
{
#if VERBOSE
printf ("%d <- temp since %d is leaf.\n", parent, parent);
#endif
memcpy (ptr_parent, temp_record, width);
break;
} /* end if */

ptr_child = base + child * width;
if (child < right) /* Is there more than one child? */
{
/* Use the biggest child. */
if (compare (ptr_child, ptr_child2 = ptr_child + width) < 0)
{
child++;
ptr_child = ptr_child2;
} /* end if ptr_child < ptr_child2 */
} /* end if child < right */

if (compare (temp_record, ptr_child) >= 0) /* Is temp_record bigger? */
{
#if VERBOSE
printf ("%d <- temp since temp is bigger than %d.\n", parent, child1);
#endif
memcpy (ptr_parent, temp_record, width);
break;
}

#if VERBOSE
printf ("%d <- %d since we're not done yet\n", parent, child1);
#endif
memcpy (ptr_parent, ptr_child, width); /* Promote by a generation */
} /* end while TRUE */

#if VERBOSE
puts ("Done heapifying.");
show_heap();
#endif
} /* end heapify */


void
show_heap ()
{
puts ("The heap:");
show_node (0);
}

void
show_node (int node_id)
{
int child1, child2, ancestor;

child1 = node_id * 2 + 1;
child2 = child1 + 1;

printf ("%.4lf\t", ((double *) base) [node_id]);
if (child1 < nelem)
show_node (child1);
else
putchar ('\n');

if (child2 < nelem)
{
for (ancestor = 1; ancestor < child2; ancestor <<= 1)
putchar ('\t');
show_node (child2);
}
} /* end show_node */

  3 Responses to “Category : C Source Code
Archive   : BFSORTS.ZIP
Filename : HSORT.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/