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

using namespace std;

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

char random_letter() {
        static string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        int pos = random_in_range(0, alphabet.length()-1);
        return alphabet[pos];
}

string random_string() {
        int length = random_in_range(3,12);
        string result = "";
        for (int i=0; i<length; i++)
                result += random_letter();
        return result;
}

void randomize(string A[], int n) {
        for (int i=0; i<n; i++)
                A[i] = random_string();
}

void swap(string & a, string & b) {
        string temp = a;
        a = b;
        b = temp;
}

bool compare(string & a, string & b) {
        if (a>b) return true;
        else if (a<b) return false;
}

void selection_sort(string A[], int size) {
        int x = 0;
        for (int i=0; i<size-1; i++) {
                x = i;
                for (int j=i+1; j<size; j++) {
                        if (compare(A[x],A[j])==true) x = j;
      }
        swap(A[x],A[i]); 
        }
}

void insertion_sort(string A[], int size) {
        for (int i=0; i<=size; i++) {
                for (int j=i-1; j>0; j--) {
                        if (compare(A[j],A[j-1])==false) {
                                swap(A[j],A[j-1]);
                        }
                }
        }
}

void bubble_sort(string A[], int size) {
        for (int i=size; i>0; i--) {
                for (int j=0; j<i-1; j++) {
                        if (compare(A[j],A[j+1])==true) swap(A[j],A[j+1]);
                }
        }
}

double getcputime(void) {
          struct timeval tim;  
          struct rusage ru;
          getrusage(RUSAGE_SELF, &ru);
          tim=ru.ru_utime;
          double t=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;
          tim=ru.ru_stime;
          t+=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;
          return t;
}

void main() {
        int size;
        double starttime, endtime;
        string sort;

        cout << "How many strings in the array?\n";
        cin >> size;
        cout << "\n";
                
        string data[size];
        randomize(data,size);
      
  	for (int i=0; i<size; i++) {
                cout << data[i] << " ";
        }

	cout << "\n\n" << "Insertion, Selection, or Bubble Sort? (Type 'Insertion', 'Selection', or 'Bubble')\n";
        cin >> sort;
        cout << "\n";

        starttime = getcputime();

        if (sort=="Insertion" || sort=="insertion") insertion_sort(data,size);
        else if (sort=="Selection" || sort=="selection") selection_sort(data,size);
        else if (sort=="Bubble" || sort=="bubble") bubble_sort(data,size);

        endtime = getcputime();

        for (int i=0; i<size; i++) {
                cout << data[i] << " ";
        }

	cout << "\n\n" << "The time taken to sort this array was: " << endtime-starttime << "\n";
}