// Chapter 9, pp 425 - 426

#include <stdlib.h> // included for rand in main

#include <iostream.h>

const int MAX_SIZE = 12;

typedef int dataType;
typedef dataType arrayType[MAX_SIZE];

void Swap(dataType& X, dataType& Y)
// ---------------------------------------------------------
// Swaps X and Y.
// Precondition: None.
// Postcondition: Contents of actual locations that X and Y
// represent are swapped.
// ---------------------------------------------------------
{
   dataType Temp = X;
   X = Y;
   Y = Temp;
}  // end Swap

void Partition(dataType A[], int F, int L, int& PivotIndex)
// ---------------------------------------------------------
// Partitions A[F..L] for quicksort.
// Precondition: F <= L; assumes pivot is A[F].
// Postcondition: Partitions A[F..L] such that:
//    S1 =  A[F..PivotIndex-1] <  Pivot
//          A[PivotIndex]      == Pivot
//    S2 =  A[PivotIndex+1..L] >= Pivot
// Calls: Swap.
// ---------------------------------------------------------
{
   // initially, everything but pivot is in unknown
   dataType Pivot = A[F];     // assumes pivot is first item
   int LastS1 = F;            // index of last item in S1
   int FirstUnknown = F + 1;  // index of first item in 
                              // unknown

   // move one item at a time until unknown region is empty
   for (; FirstUnknown <= L; ++FirstUnknown)
   {  // Invariant: A[F+1..LastS1] < Pivot
      // A[LastS1+1..FirstUnknown-1] >= Pivot

      // move item from unknown to proper region
      if (A[FirstUnknown] < Pivot)
      {  // item from unknown belongs in S1
         ++LastS1;
         Swap(A[FirstUnknown], A[LastS1]);
      }

      // else item from unknown belongs in S2
   }  // end for

   // place pivot in proper position and mark its location
   Swap(A[F], A[LastS1]);
   PivotIndex = LastS1;
}  // end Partition

void Quicksort(dataType A[], int F, int L)
// ---------------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: A[F..L] is an array.
// Postcondition: A[F..L] is sorted.
// Calls: Partition.
// ---------------------------------------------------------
{
   int PivotIndex;

   if (F < L)
   {  // create the partition: S1, Pivot, S2
      Partition(A, F, L, PivotIndex);

      // sort regions S1 and S2
      Quicksort(A, F, PivotIndex-1);
      Quicksort(A, PivotIndex+1, L);
   }  // end if
}  // end Quicksort

// ******SAMPLE MAIN PROGRAM******
main()
{  arrayType A;
   int N, Size;

   // create an array of random integers
   Size = MAX_SIZE; // size of array
   for (N = 0; N < Size; ++N)
      A[N] = rand();

   cout << "The array before sorting is:\n ";
   for (N = 0; N < Size; ++N)
      cout << A[N] << " ";
   cout << "\n";

   // sort the array
   Quicksort(A, 0, Size-1);

   cout << "The array after sorting is:\n ";
   for (N = 0; N < Size; ++N)
      cout << A[N] << " ";
   cout << "\n";
   return 0;
}  // end main