home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_09_06 / 9n06053a < prev    next >
Text File  |  1991-02-27  |  1KB  |  75 lines
  1. //      HSort.Cpp  V.2.0 - 2/27/91
  2. //
  3. //    Turbo C++ V.1.0
  4. //
  5. //    Michael Kelly - Author
  6. //
  7. //    Sorts an array of "Things" in place using 
  8. //    the HeapSort Algorithm.
  9. //
  10. #include "hsort.hpp"
  11.  
  12. static Thing tmp;         // temporary for swaps
  13.  
  14. // Exchange two Things.
  15. //
  16. inline void swap( Thing &t1, Thing &t2 )
  17. {
  18.     tmp = t2;
  19.     t2 = t1;
  20.     t1 = tmp;
  21. }
  22.  
  23. // Sift down through the heap.
  24. //
  25. void sift_heap( size_t N, size_t root_node, Thing *ptr)  
  26. {
  27.     size_t parent = root_node, child = root_node << 1;
  28.  
  29.     do  {
  30.  
  31.     if( child > N ) 
  32.         break;
  33.  
  34.     if(child != N &&
  35.         ( ptr[ child ] < ptr[ child + 1 ] ))
  36.         ++child;
  37.  
  38.     if( ! ( ptr[ parent ] < ptr[ child ] ))
  39.         break;
  40.     else  { 
  41.         swap( ptr[ child ], ptr[ parent ] );
  42.         child = ( parent = child ) << 1; 
  43.     }
  44.  
  45.     }while( 1 );
  46. }
  47.  
  48. // classic HeapSort Algorithm
  49. //
  50. void heapsort( size_t num_things, Thing *array )
  51. {
  52.     size_t root = num_things >> 1;
  53.  
  54.  
  55.     if( num_things < 2  ||  !array )
  56.     return;
  57.  
  58.     --array;  // allows indexing array from 1..N
  59.  
  60.     for( ; root > 1; --root )
  61.     sift_heap( num_things, root, array );
  62.  
  63.     for( ; num_things > 1; --num_things )  {
  64.     sift_heap( num_things, 1, array );
  65.     swap( array[ num_things ], array[ 1 ] );
  66.     }
  67.  
  68.     // "erase" tmp's "shallow copy"
  69.     // so tmp's destructor won't
  70.     // deallocate memory owned
  71.     // by another Thing
  72.     //
  73.     tmp = TheNullThing;
  74. }
  75.