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

using namespace std;

void sort(int A[], int num)
{ while (num > 0)
  { int biggestpos = 0;
    for (int i = 1; i < num; i += 1)
      if (A[i] > A[biggestpos])
        biggestpos = i;
    int temp = A[biggestpos];
    A[biggestpos] = A[num-1];
    A[num-1] = temp;
    num -= 1; } }

bool identical(int X[], int Y[], int size)
{ for (int i = 0; i < size; i += 1)
    if (X[i] != Y[i])
      return false;
  return true; }

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; }

int main(int argc, char * argv[])
{
  int num = atol(argv[1]);
  cout << "Sorting " << num << " random numbers\n";
  int * A = new int[num];
  int * B = new int[num];

  srandomdev();
  int start = 100;
  for (int i = 0; i < num; i += 1)
  { int onedn = random() % 9 + 1;
    start += onedn;
    A[i] = start;
    B[i] = start; }

  for (int i = 0; i < num; i += 1)
  { int r1 = random() % num;
    int r2 = random() % num;
    int temp = A[r1];
    A[r1] = A[r2];
    A[r2] = temp; } 

  double t1 = get_cpu_time();
  sort(A, num);
  double t2 = get_cpu_time();
  cout << "It took " << t2-t1 << " seconds\n";

  if (identical(A, B, num))
    cout << "Success\n";
  else
    cout << "Failed\n";
}