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);
    }
  }
}

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

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.