#include <iostream>
#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; }

int random_in_range(int a, int b)
{ return a + random() % (b - a + 1); }

char random_char()
{ return (char) random_in_range(97, 122); }

string random_string()
{ int length = random_in_range(5, 10);
  string s = "";
  for (int i = 0; i < length; i += 1)
    s += random_char();
  return s; }

void generate(string W[], int size)
{ for (int i = 0; i < size; i += 1)
    W[i] = random_string(); }

void sort(string W[], int size)  // in-place Insertion sort
{ for (int t = 0; t < size; t += 1)
  { string p = W[t];
    int i = 0;
    while (i < t)
    { if (W[i] > p)
        break;  
      i += 1; }
    for (int j = t; j > i; j -= 1)
      W[j] = W[j-1];
    W[i] = p; } }

int main(int argc, char * argv[])
{ if (argc != 2)
  { cout << "Give me the number on the command line\n";
    exit(1); }
  srandomdev();
  int num = atoi(argv[1]);
  string * words = new string[num];
  generate(words, num);
  double t1 = get_cpu_time();
  sort(words, num);
  double t2 = get_cpu_time();
  cout << "It took " << t2-t1 << " seconds\n";
  for (int i = 0; i < num; i += 1)
    cout << words[i] << " ";
  cout << "\n"; }