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 >
Wrap
Text File
|
1991-02-27
|
1KB
|
75 lines
// HSort.Cpp V.2.0 - 2/27/91
//
// Turbo C++ V.1.0
//
// Michael Kelly - Author
//
// Sorts an array of "Things" in place using
// the HeapSort Algorithm.
//
#include "hsort.hpp"
static Thing tmp; // temporary for swaps
// Exchange two Things.
//
inline void swap( Thing &t1, Thing &t2 )
{
tmp = t2;
t2 = t1;
t1 = tmp;
}
// Sift down through the heap.
//
void sift_heap( size_t N, size_t root_node, Thing *ptr)
{
size_t parent = root_node, child = root_node << 1;
do {
if( child > N )
break;
if(child != N &&
( ptr[ child ] < ptr[ child + 1 ] ))
++child;
if( ! ( ptr[ parent ] < ptr[ child ] ))
break;
else {
swap( ptr[ child ], ptr[ parent ] );
child = ( parent = child ) << 1;
}
}while( 1 );
}
// classic HeapSort Algorithm
//
void heapsort( size_t num_things, Thing *array )
{
size_t root = num_things >> 1;
if( num_things < 2 || !array )
return;
--array; // allows indexing array from 1..N
for( ; root > 1; --root )
sift_heap( num_things, root, array );
for( ; num_things > 1; --num_things ) {
sift_heap( num_things, 1, array );
swap( array[ num_things ], array[ 1 ] );
}
// "erase" tmp's "shallow copy"
// so tmp's destructor won't
// deallocate memory owned
// by another Thing
//
tmp = TheNullThing;
}