#include <iostream>
#include <cstdlib>
#include <string>
#include <time.h>
#include <sys/resource.h>

using namespace std;

double get_cpu_time()
{ rusage ruse;
  getrusage(RUSAGE_SELF, & ruse);
  return ruse.ru_utime.tv_sec + ruse.ru_utime.tv_usec / 1000000.0 +
         ruse.ru_stime.tv_sec + ruse.ru_stime.tv_usec / 1000000.0; }

string randstr()
{ int n = random() % 12 + 8;
  string r;
  for (int i = 0; i < n; i += 1)
    r += (char)(random() % 26 + 'a');
  return r; }

void print(string arr[], int num)
{ for (int i = 0; i < num; i += 1)
    cout << arr[i] << " ";
  cout << "\n"; }

void sort(string A[], int N)
{ int stop = N - 1;
  while (stop > 0)
  { int maxpos = 0;
    string maxstr = A[maxpos];
    for (int i = 1; i <= stop; i += 1)
      if (A[i] > maxstr)
      { maxstr = A[i];
        maxpos = i; }
    A[maxpos] = A[stop];
    A[stop] = maxstr;
    stop -= 1; } }

int main(int argc, char * argv[])
{ int num = 1024;
  if (argc > 1)
  { char * c;
    num = strtol(argv[1], & c, 10);
    if (* c != '\0')
    { cerr << "'" << argv[1] << "' is not a proper number\n";
      exit(1); } }

  string * arr = new string[num];
  srandomdev();
  for (int i = 0; i < num; i += 1)
    arr[i] = randstr();
  print(arr, num);

  double t0 = get_cpu_time();
  sort(arr, num);
  double t1 = get_cpu_time();

  cout << "it took " << t1 - t0 << " seconds.\n";
  cout << num * num / (2 * (t1 - t0)) << " operations per second\n";

  print(arr, num); }