## digitalmars.D - heap and insertion sorts

David Medlock <noone nowhere.com> writes:
Ported from public domain code.

// =====================================
// insertion sort
// =====================================
template isort(T)
{
void isort(T[] array, int delegate(T,T) compare = null)
{
int cmp( T x, T y ) { return x<y ? -1 : x==y ? 0 : 1 ;}

if ( compare is null ) compare = &cmp;

// shift elements until this value can be inserted
void reinsert( T value, int start )
{
while( start >=0 )
{
if ( cmp(array[start], value) < 0 ) break;
array[start+1]=array[start];
start--;
}
array[start+1] = value;
}

for (int i = 1; i < array.length; i++)
{
if ( cmp(array[i-1],array[i])>0 )  reinsert( array[i] , i-1 );
}
}
}

// =====================================
// Heapsort
// =====================================
template hsort(T)
{
void hsort( T[] array, int delegate(T,T) compare = null )
{
int cmp( T a, T b ) { return a<b ? -1 : a==b ? 0 : 1;}
if ( compare is null ) compare = &cmp;

int parent( int n ) { return (n&1)==0 ? (n/2)-1 : (n/2); }
int left( int n)    { return n*2 + 1; }
int right( int n )  { return n*2 + 2; }

void swap( int a, int b )
{
T temp = array[a];
array[a] = array[b];
array[b] = temp;
}

int heapsize = array.length -1 ;

void heapify( T[] array, int which )
{
int L = left(which);
int R = right(which);
int large = which;
if ( L < heapsize ) if ( compare(array[L] ,array[which] ) > 0 )
{
large = L;
}

if ( L < heapsize ) if ( compare(array[R] ,array[large] ) > 0 )
{
large = R;
}
if ( large != which )
{
swap( large, which );
heapify( array, large );
}
}

for (int i = (heapsize-1) / 2; i >= 0; i--)
{
heapify(array, i);
}

for (int i = heapsize; i > 0; i--)
{
swap( 0, heapsize );
heapsize--;
heapify(array, 0);
}
}
}
Oct 25 2006
Sean Kelly <sean f4.ca> writes:
David Medlock wrote:

Ported from public domain code.

// =====================================
// insertion sort
// =====================================
template isort(T)
{
void isort(T[] array, int delegate(T,T) compare = null)
{
int cmp( T x, T y ) { return x<y ? -1 : x==y ? 0 : 1 ;}

if ( compare is null ) compare = &cmp;

// shift elements until this value can be inserted
void reinsert( T value, int start )
{
while( start >=0 )
{
if ( cmp(array[start], value) < 0 ) break;
This should be 'compare'.
array[start+1]=array[start];
start--;
}
array[start+1] = value;
}

for (int i = 1; i < array.length; i++)
{
if ( cmp(array[i-1],array[i])>0 )  reinsert( array[i] , i-1 );
This too.
}
}
}
Sean
Oct 25 2006
David Medlock <noone nowhere.com> writes:
Sean Kelly wrote:
David Medlock wrote:

Ported from public domain code.

// =====================================
// insertion sort
// =====================================
template isort(T)
{
void isort(T[] array, int delegate(T,T) compare = null)
{
int cmp( T x, T y ) { return x<y ? -1 : x==y ? 0 : 1 ;}

if ( compare is null ) compare = &cmp;

// shift elements until this value can be inserted
void reinsert( T value, int start )
{
while( start >=0 )
{
if ( cmp(array[start], value) < 0 ) break;
This should be 'compare'.
array[start+1]=array[start];
start--;
}
array[start+1] = value;
}

for (int i = 1; i < array.length; i++)
{
if ( cmp(array[i-1],array[i])>0 )  reinsert( array[i] , i-1 );
This too.
}
}
}
Sean
Hehehe. Thanks Sean.
Oct 25 2006