//
// Quick Sort Implementation
//

extern void Swap (int&, int&);

//
// Pivot Finding
//
void
Partition (int A[], int L, int F, int &PivotIndex)
{
  int direction = 0;
  int i = L, j = F;

  while (i < j)
    {
      if (A[i] > A[j])
        {
          direction = 1 - direction;
          Swap (A[i], A[j]);
        }
      if (direction)
        j--;
      else
        i++;
    }
  PivotIndex = i;
}

void 
QuickSrt (int A[], int L, int R)
{
  int PivotIndex = 0;

  if (R > L)
    {
      Partition (A, L, R, PivotIndex);
      QuickSrt (A, L, PivotIndex - 1);
      QuickSrt (A, PivotIndex + 1, R);
    }
}

void
QuickSortR (int A[], int N)
{
  QuickSrt (A, 0, N-1);
}



#include "tlstack.h"

void
QuickSortI (int A[], int N)
{
  int PivotIndex, L, R;
  Stack<int> S;

  S.Push (0); S.Push (N-1);
  while (!S.isEmpty ())
    {
      S.Pop (R); S.Pop (L);
      if (R <= L) continue;
      Partition (A, L, R, PivotIndex); 
      S.Push (L); S.Push (PivotIndex-1); 
      S.Push (PivotIndex+1); S.Push (R); 
    }
}