#include <iostream.h>

int partition(int [], int, int);  // function prototype

int main()
{
  const int NUMEL = 7;

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

  pivot = partition(nums, 0, NUMEL-1);

  cout << "\nThe returned pivot index is " << pivot;
  cout << "\nThe list is now in the order:\n";
  for (i = 0; i < NUMEL; i++)
    cout << "  " <<nums[i];
  cout << endl;

  return 0;
}

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
}