#include <cstdlib>  // needed here to generate random numbers
#include <ctime>  // needed for measurement of clock ticks, see below
#include <iostream>
using namespace std;

void insertion_sort(int n, int* x)
{
   int sortedx[n];
   for(int i = 0; i < n; i++)
   {
      int j = 0;
      while((j < i) && (sortedx[j] < x[i])) j++;
      for(int k = i; k > j; k--) sortedx[k] = sortedx[k-1];
      sortedx[j] = x[i];
   }

   // overwrite the array x with its sorted version and return
   //
   for(int i = 0; i < n; i++) x[i] = sortedx[i];
   return;
}

int main()
{
   int n;
   cout << "How many random numbers should be generated and sorted? n = ";
   cin >> n;
   if(n < 1) return 0;
   
   // generate n random numbers
   //
   int val[n];
   srand(time(NULL));  // initialize random number generator, using time
   for(int i=0; i < n; i++) val[i] = rand();
   
   clock_t before_sorting = clock();  // time (in clock ticks) before sorting
   insertion_sort(n, val);  // sort the array
   clock_t after_sorting = clock();  // time (in clock ticks) after sorting
   
   // output the sorted array
   //
   cout << "\nSorted values:";
   for(int i = 0; i < n; i++) cout << " " << val[i];
   cout << ".\n";
   
   double milliseconds = 1000.0*(after_sorting - before_sorting)/CLOCKS_PER_SEC;
   cout << "\nTime needed for sorting: " << milliseconds << " milliseconds.\n";
   return 0;
}