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


/* Selection sorts an array.  T must have > operator and there must be a
 * function void swap (T &, T&) that swaps two instances of T.
 * Pivot is always the 0'th element
 */
template <class T>
void SelectionSortArray(T * array, int count)
{

  int maxindex, i, j;

  // Before the j-th iteration, the last j elements of the array
  // are in their correct poistions.  After j-th iteration, j+1 are.
  // Need to go for count-1 iterations
  for (j=0; j<count-1; j++) {

    // Find the max
    for (i=maxindex=0; i<count-j; i++)
      if (array[i]>array[maxindex])
	maxindex=i;

    // Put it in position count-j-1
    swap(array[maxindex], array[count-j-1]);
  }
}


/* Quick sorts an array.  T must have > operator and there must be a
 * function void swap (T &, T&) that swaps two instances of T.
 * Pivot is always the 0'th element
 */
template <class T>
void QuickSortArray(T * array, int count)
{

  if (count<=1)
    return;

  int i=0, j=count;

  // Split the array
  // pivot is in position 0; positions between 0 and i (inclusive)
  // are less than pivot, and positions between j and count are greater
  // than or equal to pivot
  while (i<j-1) {
    if (array[0]>array[i+1])
      i++;
    else
      swap(array[i+1], array[--j]);
  }
  // Now put the pivot where it belongs
  swap (array[0], array[i]);

  // Recurse on the two halves, except the pivot position, which
  // is already correct
  QuickSortArray(array, i);
  QuickSortArray(array+i+1, count-i-1);
}


/* Quick sorts an array.  T must have > operator and there must be a
 * function void swap (T &, T&) that swaps two instances of T.
 * Pivot is chosend at random
 */
template <class T>
void RandomizedQuickSortArray(T * array, int count)
{

  if (count<=1)
    return;

  int i=0, j=count;

  // First take a random element and put it in position 0 to be the pivot
  swap(array[0], array[rand()%count]);

  // Split the array
  // pivot is in position 0; positions between 0 and i (inclusive)
  // are less than pivot, and positions between j and count are greater
  // than or equal to pivot
  while (i<j-1) {
    if (array[0]>array[i+1])
      i++;
    else
      swap(array[i+1], array[--j]);
  }
  // Now put the pivot where it belongs
  swap (array[0], array[i]);

  // Recurse on the two halves, except the pivot position, which
  // is already correct
  RandomizedQuickSortArray(array, i);
  RandomizedQuickSortArray(array+i+1, count-i-1);
}

/* 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;
}