home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume34 / flogger / part01 / heap_sort.c < prev    next >
C/C++ Source or Header  |  1992-12-18  |  4KB  |  216 lines
  1.  
  2. /* 
  3.  
  4. NAME
  5.   heap sort 
  6.  
  7. DESCRIPTION
  8.  
  9.   See some of the comments below for a partial description.
  10.  
  11. AUTHORSHIP
  12.  
  13.   This version was written by mouse@larry.mcrcim.mcgill.edu
  14.   who has gracefully given me permission to include it in
  15.   this package of sort algorithms. 
  16.  
  17.   The original heapsort is credited to Williams by Knuth and
  18.   some improvements are credited to Floyd by Standish.
  19.  
  20. REFERENCES
  21.  
  22.   J. W. J. Williams, CACM 7 1964
  23.   R. W. Floyd, Algorithm 245: Treesort 3, CACM 7:12 December, 1964
  24.   Knuth, Art of Computer Programming Vol 3, page 145ff
  25.   Thomas A. Standish, Data Structure Techniques, page 91-92
  26.  
  27. COMPLEXITY
  28.  
  29.   O(n log n)
  30.   Iterative.
  31.  
  32. COPYRIGHT
  33.  
  34.   Questions about the copyright status of should be addressed
  35.   to the author.
  36.  
  37. */
  38.  
  39.  
  40. #include <stdio.h>
  41. #include <malloc.h>
  42. #include <string.h>
  43.  
  44. /* this is an interface routine that takes a parameter
  45.    list like qsort's and then calls the real heapsort. */
  46.    
  47. int heap_sort(base, nelem, width, cmpr_func)
  48.   char * base;
  49.   int nelem;
  50.   int width;
  51.   int (*cmpr_func)();
  52. {
  53.   char ** temp_in;
  54.   char * temp_out;
  55.   int i;
  56.  
  57.   temp_in = (char **) malloc(nelem * sizeof(char *));
  58.   for (i = 0; i < nelem; i++)
  59.     temp_in[i] = base+i*width;
  60.  
  61.   heapsort(temp_in, nelem, cmpr_func);
  62.  
  63.   temp_out = malloc(nelem * width);
  64.   for (i = 0; i < nelem; i++)
  65.     memcpy(temp_out+i*width, temp_in[i], width);
  66.  
  67.   memcpy(base, temp_out, nelem*width);
  68.  
  69.   free((char *) temp_in);
  70.   free(temp_out);
  71.  
  72.   return 0;
  73. }
  74.  
  75. /*
  76. From uunet!Thunder.McRCIM.McGill.EDU!mouse Fri Nov 20 04:41:30 1992
  77. Date: Fri, 20 Nov 92 05:13:19 -0500
  78. From: der Mouse  <uunet!Thunder.McRCIM.McGill.EDU!mouse>
  79. To: mikey@ontek.com
  80. Subject: Re: qucik, merge, shell and bubble sort
  81. Status: R
  82.  
  83. > I'll also be adding heapsort and shellsort algorithms; if anyone has
  84. > a qsort-like drop-in replacement for either or both of those I'd
  85. > appreciate a copy.
  86.  
  87. Note the interface difference (an extra level of pointers, which is a
  88. bit of a pain because it often means allocating an array of char *),
  89. but here's a heapsort I've been using.  (I wrote it.)
  90. */
  91.  
  92. #if 0
  93. heapsort(ptrs,nels,cmp)
  94. char **ptrs; /* should be `<unknown>**ptrs', but no such type exists */
  95. int nels;
  96. int (*cmp)();
  97. #endif
  98. /*
  99.         Sorts the ptrs vector.  (*cmp)(ptrs[i],ptrs[j]) should return:
  100.  
  101.                 < 0        if *ptrs[i] < *ptrs[j]
  102.                 = 0        if *ptrs[i] = *ptrs[j]
  103.                 > 0        if *ptrs[i] > *ptrs[j]
  104.  
  105.         For example, if the ptrs are actually pointers to int, it would
  106.         be perfectly good to write a cmp function as follows (unless the
  107.         integers are so large that overflow can occur in the subtraction):
  108.  
  109.                 int cmp(p1,p2)
  110.                 char *p1;
  111.                 char *p2;
  112.                 {
  113.                  return(*(int *)p1 - *(int *)p2);
  114.                 }
  115.  
  116.         Tip:  If the ptrs are character string pointers, the standard
  117.         strcmp() function is a good cmp function.
  118.  
  119.         The vector will be in non-decreasing order by this criterion on
  120.         return from heapsort.
  121. */
  122.  
  123. static _heapsort_bubble_up(size,ptrs,cmp)
  124. int size;
  125. char **ptrs;
  126. int (*cmp)();
  127. {
  128.  int i;
  129.  int p;
  130.  char *temp;
  131.  
  132.  i = size;
  133.  while (1)
  134.   { if (i == 0)
  135.      { return;
  136.      }
  137.     p = (i - 1) >> 1;
  138.     if ((*cmp)(ptrs[i],ptrs[p]) > 0)
  139.      { temp = ptrs[i];
  140.        ptrs[i] = ptrs[p];
  141.        ptrs[p] = temp;
  142.        i = p;
  143.      }
  144.     else
  145.      { return;
  146.      }
  147.   }
  148. }
  149.  
  150. static _heapsort_bubble_down(size,ptrs,cmp)
  151. int size;
  152. char **ptrs;
  153. int (*cmp)();
  154. {
  155.  int i;
  156.  int j;
  157.  int l;
  158.  int r;
  159.  int cl;
  160.  int cr;
  161.  char *temp;
  162.  
  163.  i = 0;
  164.  while (1)
  165.   { if (i >= size)
  166.      { return;
  167.      }
  168.     l = i + i + 1;
  169.     r = l + 1;
  170.     cl = (l >= size) ? 1 : ((*cmp)(ptrs[i],ptrs[l]) >= 0);
  171.     cr = (r >= size) ? 1 : ((*cmp)(ptrs[i],ptrs[r]) >= 0);
  172.     switch ((cl<<1)|cr)
  173.      { case 0:
  174.           j = ((*cmp)(ptrs[l],ptrs[r]) > 0) ? l : r;
  175.           break;
  176.        case 1:
  177.           j = l;
  178.           break;
  179.        case 2:
  180.           j = r;
  181.           break;
  182.        case 3:
  183.           return;
  184.      }
  185.     temp = ptrs[j];
  186.     ptrs[j] = ptrs[i];
  187.     ptrs[i] = temp;
  188.     i = j;
  189.   }
  190. }
  191.  
  192. heapsort(ptrs,nels,cmp)
  193. char **ptrs;
  194. int nels;
  195. int (*cmp)();
  196. {
  197.  int size;
  198.  char *temp;
  199.  
  200.  if (nels <= 1)
  201.   { return;
  202.   }
  203.  size = 1;
  204.  while (size < nels)
  205.   { _heapsort_bubble_up(size,ptrs,cmp);
  206.     size ++;
  207.   }
  208.  while (size > 1)
  209.   { size --;
  210.     temp = ptrs[size];
  211.     ptrs[size] = ptrs[0];
  212.     ptrs[0] = temp;
  213.     _heapsort_bubble_down(size,ptrs,cmp);
  214.   }
  215. }
  216.