// quicksort.cc  Template-Version
using namespace std;
#include <iostream>

int scount=0;      // Zaehler fuer die Aufrufe von Swap
template <class T>                  // Swap template
inline void Swap(T& x, T& y) {
  T tmp = x;
  x = y; y = tmp;
  scount++;
}
template <class T>                 // Ausgabe-Template
ostream& out(T v[], int size) {
  for (int i=0; i<size; i++)
    cout << v[i] << ' ';
  return cout;
}
template <class T>             // Quicksort-Template
void quicksort(T v[], int n) { // cf. K&R, p.87, dort fuer C und festen Typ
  if(n <= 1)
    return;
  int last = 0;
  for (int i = 1; i < n; i++)
    if (v[0] > v[i])
      Swap(v[++last], v[i]);
  Swap(v[0],v[last]);
  quicksort(v, last); quicksort(v+last+1, n-last-1);
}
#define size(A) (sizeof((A))/sizeof((A)[0]))

// Diese Arrays verschiedener Typen werden sortiert:
int    a[] = { 3, 1, 4, 1, 5, 9, 2, 6, 3, 1, 4, 1, 5, 9, 2, 6};
float  b[] = { 3.1, 4.3, 5.9, 2.7, 5.3, 5.9, 9.7, 9.9,
	       3.2, 4.1, 5.7, 2.6, 5.4, 5.8, 9.3, 9.3};
string s[] = { "Sonntag",  "Montag", "Dienstag", "Mittwoch", "Donnerstag",
"Freitag", "Samstag", "Mittwoch", "Donnerstag", "Freitag", "Samstag" };
int main() {
  scount=0;
  quicksort(a,size(a)); out(a,size(a))<<'\n';
  cout<<scount<<'\n';scount=0;
  quicksort(b,size(b)); out(b,size(b))<<'\n';
  cout<<scount<<'\n';scount=0;
  quicksort(s,size(s)); out(s,size(s))<<'\n';
  cout<<scount<<'\n';scount=0;
}