//
//  File:  basic_quick.h
//
//    This is the basic version of the quicksort algorithm, with the
//    Left element used as the pivot at all times and no use of
//    insertion sort for small intervals.  Note that the first while
//    loop includes a test to see if i has gone out of range.  This
//    would occur if the pivot were the smallest element in the
//    interval from Left to Right.
//

template <class T>
inline void
Swap( T & A, T & B )
{
  T Tmp = A;
  A = B;
  B = Tmp;
}

template <class T>
void
B_Q_Sort( T A[ ], int Left, int Right )
{
  if ( Left >= Right ) return;

  T Pivot = A[ Left ];
  unsigned int i = Left, j = Right+1;

  for( ; ; )     {
    while( A[ ++i ] < Pivot && i < Right );
    while( A[ --j ] > Pivot );
    if( i < j )
      Swap( A[ i ], A[ j ] );
    else
      break;
  }

  Swap( A[ j ], A[ Left ] ); // Place the pivot in its final position

  B_Q_Sort( A, Left, j - 1 );
  B_Q_Sort( A, j + 1, Right );
}

template <class T>
void
B_Quick_Sort( T A[ ], int N )
{
  B_Q_Sort( A, 0, N-1 );
}


//
//  File: quick.h
//
//   This is the enhanced version of quick sort with median of 3
//   pivoting and use of insertion sort for small sublists.
// 

const int Cutoff = 14;   // sublists with Cutoff or fewer elements are
			 // sorted using insertion sort


template <class T>
inline void
Swap( T & A, T & B )
{
  T Tmp = A;
  A = B;
  B = Tmp;
}


//  Return the median of A[Left], A[Center] and A[Right].  Leave the
//  smallest value in A[Left], the largest value in A[Right] and the
//  median value in A[Right-1].
//
template <class T>
T &
Median3( T A[ ], int Left, int Right )
{
  unsigned int Center = ( Left + Right ) /2;

  if( A[ Left ] > A[ Center ] )
    Swap( A[ Left ], A[ Center ] );
  if( A[ Left ] > A[ Right ] )
    Swap( A[ Left ], A[ Right ] );
  if( A[ Center ] > A[ Right ] )
    Swap( A[ Center ], A[ Right ] );

  // Result: A[ Left ] <= A[ Center ] <= A[ Right ].
  // Now shift pivot to position Right-1 and return the pivot.

  Swap( A[ Center ], A[ Right - 1 ] );
  return A[ Right - 1 ];
}


template <class T>
void
Q_Sort( T A[ ], int Left, int Right )
{
  if( Left + Cutoff <= 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;
    }

    //  Place the pivot in its correct position.  Note that this
    //  position is A[i].  In the basic version it was A[ j ].
    //  Can you figure out why?
    //
    Swap( A[ i ], A[ Right-1 ] );

    Q_Sort( A, Left, i-1 );
    Q_Sort( A, i+1, Right );
  }
}

// templates for the main sort function called by the Quick_Sort
// driver function.


template <class T>
void
Quick_Sort( T A[ ], int N )
{
  Q_Sort( A, 0, N-1 );
  Insertion_Sort( A, N );
}


//
//  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 ];
}