www.pudn.com > HSORT.rar > HSORT.C

/***********************************************************************/ 
/*  HSORT(): Heap Sort function.                                       */ 
/*  See the function declaration for calling information.              */ 
/*  Set STANDALONE != 0 to compile a shell to test the sucker;         */ 
/*    to compile just hsort() and its supporting functions, set        */ 
/*    STANDALONE = 0.                                                  */ 
/* DEBUG determines how much debugging info is displayed; 0 is none.   */ 
/* TRACE determines what level of tracing information is displayed;    */ 
/*    0 is none.                                                       */ 
/* Function is by Bruce Feist; please contact me on CompuServe with    */ 
/*    a message on BORPRO or through EASYPLEX if you have any          */ 
/*    questions or problems.                                           */ 
/* Feel free to make use of this code in your own programs.            */ 
/***********************************************************************/ 
 
#define DEBUG 0 
#define STANDALONE 0 
#define TRACE 0 
 
#include  
#include  
#include  
#include  
#include  
 
static void pascal swap (unsigned int, unsigned int); 
static void pascal buildheap (void); 
static void pascal heapify (unsigned int, unsigned int); 
void       hsort (void *, unsigned int, unsigned int, int (*)()); 
 
#if STANDALONE 
static int int_compare (int *, int *); 
static void showarray (int *, unsigned int, unsigned int); 
 
void 
main() 
{ 
  unsigned int n_entries, entry_num; 
  int *entries; 
 
  printf ("How many entries do you wish to sort?  "); 
  scanf ("%d", &n_entries); 
  entries = (int *) malloc (n_entries * sizeof(int)); 
 
  for (entry_num = 0; entry_num < n_entries; entry_num++) 
  { 
    printf ("Enter #%d:  ", entry_num); 
    scanf ("%d", entries + entry_num); 
    } 
 
  printf ("\n"); 
 
  hsort (entries, n_entries, sizeof (int), int_compare); 
 
  showarray (entries, 0, n_entries - 1); 
 
  exit (0); 
  } 
 
 
int 
int_compare (i, j) 
int *i, *j; 
{ 
  return (*i - *j); 
  } 
 
 
void 
showarray(base, bot, top) 
int *base; 
unsigned int bot, top; 
{ 
  unsigned int i; 
 
  for (i=bot; i<=top; i++) 
    printf("%4d", base[i]); 
  printf ("\n"); 
  } 
 
#endif   /* STANDALONE */ 
 
 
static int (*static_compare) (void *, void *), static_width, static_n_elements; 
static void *temp_element, *static_base; 
 
void 
hsort(base, n_elements, element_width, compare) 
/***************************************************************************/ 
/* Heap Sort routine -- similar in calling sequence to standard 'qsort()'  */ 
/* Base is a pointer to an array                                           */ 
/* n_elements is the number of elements in the array                       */ 
/* element_width is the width of each element in bytes                     */ 
/* compare is a function of two pointers (each to an element of the array) */ 
/*    returning a negative value if the first is smaller, a positive value */ 
/*    if the second is smaller, or 0 if they should be sorted the same.    */ 
/* Warning!  This function will halt your program if it can't allocate     */ 
/*    element_width bytes using malloc().                                  */ 
/***************************************************************************/ 
 
void *base; 
unsigned int  n_elements, element_width; 
int           (*compare)(); 
{ 
  register unsigned int i; 
 
#if TRACE >= 1 
  printf("hsort(base at %lX, %u elements, width %u, compare at %ld)\n", 
         (long) base, n_elements, element_width, (long) compare); 
#endif 
 
  /* this lets us reference elements of array as 1 to n */ 
 
  (char *) base -= element_width; 
 
  /*  The following assignments to static variables reduce the */ 
  /* overhead of subroutine calls later.                       */ 
 
  static_width = element_width; 
  static_compare = compare; 
  static_n_elements = n_elements; 
  static_base = base; 
 
  temp_element = malloc (element_width); 
 
  if (temp_element == NULL) 
  { 
    fputs ("Unable to allocate room for a temporary element in hsort().\n", 
           stderr); 
    exit (1); 
    } 
 
 
  buildheap (); 
 
  for (i = n_elements; i>1; i--) 
  { 
    swap (1, i); 
    heapify (1, i-1); 
    } 
 
  free (temp_element); 
  } 
 
 
static void pascal 
swap (i, j) 
unsigned int i,j; 
 
{ 
  register int temp_int; 
  long temp_long; 
 
#if TRACE >= 2 
  printf("swap (i=%d, j=%d) called.\n",i,j); 
#endif 
 
  switch (static_width) 
  { 
    case sizeof (int): temp_int = ((int *) static_base) [i]; 
                       ((int *) static_base) [i] = ((int *) static_base) [j]; 
                       ((int *) static_base) [j] = temp_int; 
                       break; 
 
    case sizeof(long): temp_long = ((long *) static_base) [i]; 
                       ((long *) static_base) [i] = ((long *) static_base) [j]; 
                       ((long *) static_base) [j] = temp_long; 
                       break; 
 
    case sizeof(char): temp_int = ((char *) static_base) [i]; 
                       ((char *) static_base) [i] = ((char *) static_base) [j]; 
                       ((char *) static_base) [j] = (char) temp_int; 
                       break; 
 
    default:           memcpy (temp_element, 
                               (char *) static_base + i*static_width, 
                               static_width); 
                      memcpy ((char *) static_base + i*static_width, 
                              (char *) static_base + j*static_width, 
                              static_width); 
                      memcpy ((char *) static_base + j*static_width, 
                              temp_element, 
                              static_width); 
                      break; 
    }  /* end of switch */ 
 
#if TRACE >= 2 
  printf ("swap exited.\n"); 
#endif 
  } 
 
 
static void pascal 
buildheap() 
 
{ 
  register unsigned int element_number; 
 
#if TRACE >= 2 
  printf("buildheap() called.\n"); 
#endif 
 
  for (element_number = static_n_elements >> 1; 
       element_number >= 1; 
       element_number--) 
  { 
#if DEBUG >= 2 
    printf ("buildheap calls heapify (%d, %d).\n", 
            element_number, static_n_elements); 
#endif 
    heapify(element_number, static_n_elements); 
    } 
 
#if TRACE >= 2 
  printf ("buildheap exited.\n"); 
#endif 
  } 
 
 
#define son1(i)    (i << 1) 
#define son2(i)    ((i << 1) + 1) 
#define pointer(i) ((char *) static_base + i * static_width) 
#define child_count(i, j) \ 
     (j > son1(i) \ 
       ? 2 \ 
       : j < son1(i) \ 
          ? 0 \ 
          : 1) 
 
 
static void pascal 
heapify (i,j) 
 
unsigned int i, j; 
{ 
  /* The following are static to avoid recursive stack overhead */ 
 
  static unsigned int son1i, son2i; 
  static void *pson1, *pson2, *pi; 
  static unsigned int k; 
 
#if TRACE >= 3 
  printf("heapify(i=%d, j=%d) called.\n", i, j); 
#endif 
 
  son1i = son1 (i); 
  son2i = son2 (i); 
  pson1 = pointer (son1i); 
  pson2 = pointer (son2i); 
  pi    = pointer (i); 
 
#if DEBUG >= 2 
  printf ("child_count (%d) = %d.\n", i, child_count(i, j)); 
#endif 
 
  switch (child_count (i, j)) 
  { 
    case 0: break; 
 
    case 2: { 
              k = (*static_compare) (pson1, pson2) > 0 ? son1i : son2i; 
              if ((*static_compare) (pi, pointer (k)) < 0) 
              { 
#if STANDALONE && DEBUG >= 1 
                printf ("heapify changes\n"); 
                showarray (static_base, 1, static_n_elements); 
#endif 
 
                swap (i, k); 
                heapify (k, j); 
 
#if STANDALONE && DEBUG >= 1 
                printf ("into\n"); 
                showarray (static_base, 1, static_n_elements); 
#endif 
                } 
              break; 
            }  /* end case */ 
 
    case 1: if ((*static_compare) (pi, pson1) < 0) 
            { 
#if STANDALONE && DEBUG >= 1 
              printf ("heapify changes\n"); 
              showarray (static_base, 1, static_n_elements); 
#endif 
 
              swap (i, son1i); 
              heapify (son1i, j); 
 
#if STANDALONE && DEBUG >= 1 
              printf ("into\n"); 
              showarray (static_base, 1, static_n_elements); 
#endif 
              } 
            break; 
    }  /* end of case */ 
 
#if TRACE >= 3 
  printf ("heapify exited.\n"); 
#endif 
  }