#include <iostream>
#include <cstdlib>
using namespace std;


/* Bubble sorts an array.  T must have > operator and there must be a
 * function void swap (T &, T&) that swaps two instances of T.
 */
template <class T>
void BubbleSortArray(T * array, int count)
{

  int i, j;
  bool stillSwapping=true;

  // j is the index of the first element of the part that is already sorted
  for (j=count; stillSwapping; j--) {

    stillSwapping=false;

    for (i=0; i<j-1; i++) {
      if (array[i]>array[i+1]) {
	// swap if out of order
        swap (array[i], array[i+1]);
	stillSwapping=true;
      }

    }
  }
}

/* Prints an array in the following format: first the number of elements
 * in the array, then colon, then comma-separated, the elements themselves,
 * then newline.  There must be a function
 * istream &operator<<(ostream &, const T &)
 * defined.
 */
template <class T>
void PrintArray(const T * array, int count)
{
  int i;

  cout << count << ": ";
  for (i = 0; i < count; i++) {
    if (i!=0) 
      cout << ", ";
    cout << array[i];
  }

  cout<<endl;
}



/* Inputs an array in the following format: first the number of elements
 * in the array, then space, then (space-separated) the elements themselves.
 * Assumes the input is in the right format.  Returns false if cannot allocate
 * the array.  There must be a function
 * istream &operator>>(istream &, T &)
 * defined.
 */
template <class T>
bool InputArray(T *& array, int & count)
{
  int i;

  cin >> count;
  array = new (nothrow) T[count];
  if (array == NULL)
    return false;
  for (i=0; i<count; i++)
    cin >> array[i];
  return true;
}