// Chapter 9, pp 410 - 411

#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 BubbleSort(dataType A[], int N)
// ---------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: A is an array of N items.
// Postcondition: The array A is sorted into ascending 
// order; N is unchanged.
// Calls: Swap.
// ---------------------------------------------------
{
   enum boolean {FALSE, TRUE};
   boolean Sorted = FALSE;  // FALSE when swaps occur

   for (int Pass = 1; (Pass < N) && !Sorted; ++Pass)
   {  // Invariant: A[N+1-Pass..N-1] is sorted
      //            and > A[0..N-Pass]
      Sorted = TRUE;  // assume sorted
      for (int Index = 0; Index < N-Pass; ++Index)
      {  // Invariant: A[0..Index-1] <= A[Index]
			int NextIndex = Index + 1;
         if (A[Index] > A[NextIndex])
         {  // exchange items
            Swap(A[Index], A[NextIndex]);
            Sorted = FALSE;  // signal exchange
         }  // end if
      }  // end for

      // Assertion: A[0..N-Pass-1] < A[N-Pass]
   }  // end for
}  // end BubbleSort

// ******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
   BubbleSort(A, Size);

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