//
//  File: select.h
//
//   This is the quick select function.  It rearranges list A so that
//   the A[i] <= A[Loc] for 0 <= i < Loc and A[i] >= A[Loc] for Loc <=
//   i <= N-1.  It then returns A[Loc].   It is very similar to the
//   enhanced version of quicksort, but instead of continuing to sort
//   both sublists, it just picks the sublist that must contain the
//   final value of A[Loc] and continues to work on it.  
// 

const int SCutoff = 4;  // sublists with SCutoff or fewer elements are
		       // sorted using insertion sort

template <class T>
T
Quick_Select( T A[ ], int N, int Loc )
{
  int left=0;
  int right=N-1;

  while ( left + SCutoff <= right ) {
    T Pivot = Median3( A, left, right );
    unsigned int i = left, j = right - 1;

    for( ; ; ) {
      while( A[ ++i ] < Pivot );
      while( A[ --j ] > Pivot );
      if( i < j )
	Swap( A[ i ], A[ j ] );
      else
	break;
    }
    Swap( A[ i ], A[ right-1 ] );  // Move the pivot to its final position.  

    if ( Loc < i ) {
      right = i-1;
    }
    else if ( Loc > i ) {
      left = i+1;
    }
    else 
      return A[i];
  }


  //  Now, run insertion sort over the interval left .. right and
  //  then return the value at Loc.
  // 
  T tmp;
  for( int i = left+1; i <= right; i++ ) {
    tmp = A[ i ];
    int j;
    for( j= i-1; j >= left && tmp < A[ j ]; j-- )
      A[ j+1 ] = A[ j ];
    A[ j+1 ] = tmp;
  }
  return A[ Loc ];
}