// Measure execution times of bubble sort vs. the STL implementation
// of sort.
//
// Usage:
//    ./<exec name> <size of list>

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;


//
// Given a vector if ints, bubble sort it.
//
void bubbleSort(vector<int> & arr) {
  int i, j;
  int n = arr.size();
  for (i = 0; i < n-1; i++)  {    
    // Last i elements are already in place   
    for (j = 0; j < n-i-1; j++) {
      if (arr[j] > arr[j+1])
        swap(arr[j], arr[j+1]);
    }
  }
}


int main(int argc, char *argv[]) {
  
  if (argc < 2) { 
  	cout << "Usage: " << argv[0] << " <size> \n"; 
    exit(1);
  }
  int size = atoi(argv[1]);
  
  vector<int> v,w;
  
  // initialize the random seed
  srand(time(NULL));
  
  // fill the v vector with random integers
  for (unsigned int i = 0; i < size; i++) 
  	v.push_back(rand() % size);
  
  // copy v to w
  w = v;
  
  double elapsed_secs;

  // measure time to bubble sort
  clock_t begin = clock();
  bubbleSort(v);
  clock_t end = clock();

  elapsed_secs = static_cast<double>(end - begin) / CLOCKS_PER_SEC;
  cout << "\nTime elapsed for Bubblesort: " << elapsed_secs << " seconds\n";
  
  // measure time to sort using the STL sort algorithm
  begin = clock();
  sort(w.begin(),w.end());
  end = clock();

  elapsed_secs = static_cast<double>(end - begin) / CLOCKS_PER_SEC;
  cout << "Time elapsed for STL sort: " << elapsed_secs << " seconds\n";
  
  if ( is_sorted(v.begin(),v.end()) && is_sorted(w.begin(),w.end()) ) 
    cout << "Congrats! Both vectors were properly sorted!\n\n";
  else 
    cout << "At least one of the algorithms returned an unsorted vector.\n\n"; 
  
  return 0;
}