//
//  In this example we sort template arrays
//    See pages 347--353 of Budd's book

#ifndef QUICKSORT_H
#define QUICKSORT_H


// This function is already defined in STL. Comment out 
//  if  stl_algobase.h  or somesuch is included
template< class T >
void swap( T& x, T& y ){
  T z = x;
  x = y;
  y = z;
}  

template< class T >
int pivot( T a[], int start, int stop, int pos ){
  
  swap( a[start], a[pos] );  

  int low = start + 1;
  int high = stop;

  while( low <= high ){
    if( a[low] < a[start] ) 
      low++;
    else { 
      if ( a[high] < a[start] )
        swap( a[low], a[high] );
      else
	high--;
    } 
  }

  swap( a[start], a[--low] );  // swap the pivot elt back into place

  return low;   
}

template< class T >
void quicksort( T a[], int low, int high ){

  if( low >= high ) return;

  int pivotIndex = pivot( a, low, high, (low+high)/2 );

  if( low < pivotIndex ) 
    quicksort( a, low, pivotIndex );
  if( pivotIndex < high )
    quicksort( a, pivotIndex + 1, high );

}

//----------------------------------------------------------------------

// the following is a somewhat ugly method of sorting two arrays,
// the first sorted, and the second being swapped in sync with the
// first one.

template< class T, class S >
void swap_two( T& x, T& y, S& a, S& b ){
  T z = x;
  x = y;
  y = z;
  S c = a;
  a = b;
  b = c;
}  

template< class T, class S >
int pivot_two( T a[], int start, int stop, int pos, S z[]){
  
  swap_two( a[start], a[pos], z[start], z[pos] );  

  int low = start + 1;
  int high = stop;

  while( low <= high ){
    if( a[low] < a[start] ) 
      low++;
    else { 
      if ( a[high] < a[start] )
        swap_two( a[low], a[high], z[low], z[high] );
      else
	high--;
    } 
  }

  low--;
  swap_two( a[start], a[low], z[start], z[low] );  
           // swap the pivot elt back into place

  return low;   
}

template< class T, class S >
void quicksort_two( T a[], int low, int high, S z[] ){

  if( low >= high ) return;

  int pivotIndex = pivot_two( a, low, high, (low+high)/2, z );

  if( low < pivotIndex ) 
    quicksort_two( a, low, pivotIndex, z );
  if( pivotIndex < high )
    quicksort_two( a, pivotIndex + 1, high, z );

}



#endif  // QUICKSORT_H