#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

void quickSort(int arr[], int left, int right) {
  int i = left, j = right; int tmp; int pivot = arr[(left + right) / 2];
  
  /* partition */
  while (i <= j) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i <= j) {
      tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
      i++;
      j--;
    }
  }
  /* recursion */
  if (left < j) quickSort(arr, left, j);
  if (i < right) quickSort(arr, i, right);
}

template <class E> void quickSort(E arr[], int left, int right) {
  int i = left, j = right; E tmp; E pivot = arr[(left + right) / 2];
  
  /* partition */
  while (i <= j) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i <= j) {
      tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
      i++;
      j--;
    }
  }
  /* recursion */
  if (left < j) quickSort(arr, left, j);
  if (i < right) quickSort(arr, i, right);
}

class TracedElement {
private:
  static int assigns;
  static int comparisons;
  int value;
public:
  TracedElement() { this->value = 0; }
  TracedElement(int value) { this->value = value; }
  friend ostream &operator<<(ostream &os,const TracedElement &e);
  bool operator<(const TracedElement &e) const {
    comparisons++;
    return this->value<e.value;
  }
  bool operator>(const TracedElement &e) const {
    comparisons++;
    return this->value>e.value;
  }
  const TracedElement &operator=(const TracedElement &e) {
    assigns++;
    this->value = e.value;
    return *this;
  }
  static void initStats() {
    assigns = comparisons = 0;
  }
  static void showStats() {
    cout << "assigns=" << assigns << " comparisons=" << comparisons << endl;
  }
};

ostream &operator<<(ostream &os,const TracedElement &e) {
  return os << e.value;
}

int myrand() {
  return rand()%20;
}

int TracedElement::assigns = 0;
int TracedElement::comparisons = 0;

int main() {
  const int L = 30;
  int array[L];
  generate(array,array+L,myrand);
  copy(array,array+L,ostream_iterator<int>(cout," ")); cout << endl;
  quickSort(array,0,L-1);
  copy(array,array+L,ostream_iterator<int>(cout," ")); cout << endl;

  TracedElement::initStats();
  TracedElement array2[L];
  generate(array2,array2+L,myrand);
  copy(array2,array2+L,ostream_iterator<TracedElement>(cout," ")); cout << endl;
  quickSort(array2,0,L-1);
  copy(array2,array2+L,ostream_iterator<TracedElement>(cout," ")); cout << endl;
  TracedElement::showStats();

  TracedElement::initStats();
  generate(array2,array2+L,myrand);
  copy(array2,array2+L,ostream_iterator<TracedElement>(cout," ")); cout << endl;
  quickSort(array2,0,L-1);
  copy(array2,array2+L,ostream_iterator<TracedElement>(cout," ")); cout << endl;
  TracedElement::showStats();

  return 0;
}