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

using namespace std;

double get_cpu_time()
{ struct 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; }

void sort(string data[], string sorted[], int N)
{ int first = 0;
  while (first < N)
  { string x = data[first];
    int i;
    for (i = 0; i < first; i += 1)
      if (x <= sorted[i])
        break;
    for (int j = first; j >= i; j -= 1)
      sorted[j] = sorted[j-1];
    sorted[i] = x;
    first += 1; } }

int main(int argc, char * argv[])
{ srandomdev();
  if (argc != 2)
  { cerr << "Give number of words on the command line\n";
    exit(1); }
  int amt = atoi(argv[1]);

  string * orig = new string[amt];
  string * data = new string[amt];
  string * sorted = new string[amt];

  ifstream inf;
  inf.open("/home/www/dics/unabr.txt");
  if (inf.fail())
  { cerr << "Can't open file\n";
    exit(1); }
  for (int i = 0; i < amt; i += 1)
  { inf >> data[i];
    if (inf.fail())
    { cerr << "File is too short\n";
      exit(1); }
    orig[i] = data[i]; }

  for (int i = 0; i < amt * 2; i += 1)
  { int pos1 = random() % amt;
    int pos2 = random() % amt;
    swap(data[pos1], data[pos2]); }

  double t1 = get_cpu_time();
  sort(data, sorted, amt);
  double t2 = get_cpu_time();

  bool same = true;
  for (int i = 0; i < amt; i += 1)
    if (sorted[i] != orig[i])
    { same = false;
      break; }

  if (! same)
    cout << "SORTING FAILED\n";
  cout << "It took " << t2-t1 << " seconds to sort " << amt << " strings\n";
  inf.close();
  delete [] data;
  delete [] orig;
  delete [] sorted; }