#include <iostream.h>

void quicksort(int [], int, int);  // function prototypes
int partition(int [], int, int);

int main()
{
  const int NUMEL = 7;

  int nums[NUMEL] = {67,32,45,73,98,101,99};
  int i;

  quicksort(nums, 0, NUMEL-1);

  cout << "\nThe sorted list, in ascending order, is:\n";
  for (i = 0; i < NUMEL; i++)
    cout << "  " <<nums[i];
  cout << endl;

  return 0;
}

void quicksort(int num[], int lower, int upper)
{
  int i, j, pivot;

  pivot = partition(num,lower, upper);

  if (lower < pivot)
     quicksort(num, lower, pivot - 1);
  if (upper > pivot)
     quicksort(num, pivot + 1, upper);

  return;
}


int partition(int num[], int left, int right)
{
  int pivot, temp;

  pivot = num[left];  // "capture" the pivot value, which frees up one slot
  while (left < right)
  {
      // scan from right to left
    while(num[right] >= pivot && left < right)  // skip over larger or equal values
      right--;
    if (right != left)
    {
      num[left] = num[right];   // move the higher value into the available slot
      left++;
    }
      // scan from left to right
    while (num[left] <= pivot && left < right) // skip over smaller or equal values
      left++;
    if (right != left)
    {
      num[right] = num[left];  // move lower value into the available slot
      right--;
    }
  }
  num[left] = pivot;  // move pivot into correct position

  return left;       // return the pivot index
}