aads2

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <chrono>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <random>

using namespace std;
int* selection_sort(int arr[], int sizearr)
{
    int smallest = 0;
    int k = 0;
    for (int i = 0; i < sizearr - 1; i++)
    {
        k = i;
        smallest = arr[i];
        for (int j = i + 1; j < sizearr; j++)
        {
            if (arr[j] < smallest) {
                k = j;
                smallest = arr[j];
            }
        }
        arr[k] = arr[i];
        arr[i] = smallest;
    }
    return arr;
}
void selectionstring(vector<string> &strings) {
    typedef vector<string>::size_type size_type;
    string smallest = "0";
    int k = 0;
    for (size_type i = 0; i < strings.size() - 1; i++) // for n-1 passes
    {
        k = i;
        smallest = strings[i];
        for (int j = i + 1; j < strings.size(); j++)
        {
            if (strings[j] < smallest) {
                k = j;
                smallest = strings[j];
            }
        }
        strings[k] = strings[i];
        strings[i] = smallest;
    }
}

int* bubble_sort(int arr[], int sizearr)
{

    for (int i = 0; i < sizearr; i++) {
        for (int j = 1; j < sizearr; j++) {
            if (arr[j - 1] > arr[j]) {
                swap(arr[j - 1], arr[j]);
            }
        }
    }
    return arr;
}
void bubblestring(vector<string> &strings) {
    typedef vector<string>::size_type size_type;
    for (size_type i = 1; i < strings.size(); i++) // for n-1 passes
    {
        for (size_type j = 0; j < (strings.size() - 1); j++)
        {
            if (strings[j] > strings[j + 1])
            {
                swap(strings[j], strings[j + 1]);
            }
        }
    }
}

int* bubble_sort2(int arr[], int sizearr) //check if changes were made
{
    int help = 0;
    for (int i = 0; i < sizearr; i++) {
        help = 0;
        for (int j = 1; j < sizearr; j++) {
            if (arr[j - 1] > arr[j]) {
                swap(arr[j - 1], arr[j]);
                help = 1; //swap has occured
            }
        }
        if (help == 0) //if no swap occured in inner loop then stop
            break;
    }
    return arr;
}
void bubblestring2(vector<string> &strings) ////check if changes were made
{
    typedef vector<string>::size_type size_type;
    int help = 0;
    for (size_type i = 1; i < strings.size(); i++) // for n-1 passes
    {
        help = 0;
        for (size_type j = 0; j < (strings.size() - 1); j++)
        {
            if (strings[j] > strings[j + 1])
            {
                swap(strings[j], strings[j + 1]);
                help = 1;
            }
        }
        if (help == 0) //if no swap occured in inner loop then stop
            break;
    }
}

int* bubble_sort3(int arr[], int sizearr) //(doesn't check the already sorted elements)
{
    int sorted = 0;
    int i = 0, j = 1;

    while (sorted == 0) {
        sorted = 1;
        for (i = 0; i < sizearr - j; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                sorted = 0;
            }
        }
        j++;
    }
    return arr;
}
void bubblestring3(vector<string> &strings) //(doesn't check the already sorted elements)
{
    typedef vector<string>::size_type size_type;
    int sorted = 0;
    int i = 0, j = 1;

    while (sorted == 0)
    {
        sorted = 1;
        for (size_type i = 0; i < strings.size() - j; i++)
        {
            if (strings[i] > strings[i + 1])
            {
                swap(strings[i], strings[i + 1]);
                sorted = 0;
            }
        }
        j++;
    }
}

int* insertion_sort(int arr[], int sizearr)
{
    int x = 0;
    int j = 0;
    for (int i = 1; i < sizearr; i++) {
        x = arr[i];
        j = i - 1;
        while (j >= 0 && x < arr[j]) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = x;
    }
    return arr;
}
void insertionstring(vector<string> &strings) {
    typedef vector<string>::size_type size_type;
    string x = "0";
    int j = 0;
    for (int i = 1; i < strings.size(); i++) {
        x = strings[i];
        j = i - 1;
        while (j >= 0 && x < strings[j]) {
            strings[j + 1] = strings[j];
            j = j - 1;
        }
        strings[j + 1] = x;
    }
}

int* insertion_sort2(int arr[], int sizearr) //insertion with guard
{
    int smallest = arr[0];
    int arr0 = arr[0];
    for (int i = 1; i < sizearr; i++) { //check position of smallest element
        if (arr[i] < smallest)
            smallest = i;
    }
    swap(arr[0], arr[smallest]); //put smallest element at the zeroth array index
    int x = 0;
    int j = 0;
    for (int i = 0; i < sizearr; i++) {
        x = arr[i];
        j = i - 1;
        while (x <= arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = x;
    }
    return arr;
}
void insertionstring2(vector<string> &strings) {
    typedef vector<string>::size_type size_type;

    string smallest = "zzz";
    int smallestidx = 0;
    string arr0 = strings[0];
    for (size_type i = 1; i < strings.size(); i++) { //check position of smallest element
        if (strings[i] < strings[smallestidx])
            smallestidx = i;
    }
    swap(strings[0], strings[smallestidx]); //put smallest element at the zeroth array index
    string x = "zzz";
    int j = 0;
    for (size_type i = 1; i < strings.size(); i++) {
        x = strings[i];
        j = i - 1;
        while (x <= strings[j]) {
            strings[j + 1] = strings[j];
            j--;
        }
        strings[j + 1] = x;
    }
}

int* shell1(int arr[], int sizearr)
{
    int h = 1;
    int x, j;
    while (h < sizearr / 9) {
        h = 3 * h + 1;
    }
    while (h > 0) {
        for (int i = h; i < sizearr; i++) {
            x = arr[i];
            j = i;
            while (j >= h && x < arr[j - h]) {
                arr[j] = arr[j - h];
                j = j - h;
            }
            arr[j] = x;
        }
        h = h / 3;
    }
    return arr;
}
void shellstring(vector<string> &strings) //pivot is first value
{
    typedef vector<string>::size_type size_type;
    int h = 1;
    string x;
    int j;
    while (h < strings.size() / 9) {
        h = 3 * h + 1;
    }
    while (h > 0) {
        for (int i = h; i < strings.size(); i++) {
            x = strings[i];
            j = i;
            while (j >= h && x < strings[j - h]) {
                strings[j] = strings[j - h];
                j = j - h;
            }
            strings[j] = x;
        }
        h = h / 3;
    }

}

int* shell2(int arr[], int sizearr)
{
    int h = sizearr / 2;
    int x, j;
    while (h < sizearr) {
        h = 3 * h + 1;
    }
    while (h > 0) {
        for (int i = h; i < sizearr; i++) {
            x = arr[i];
            j = i;
            while (j >= h && x < arr[j - h]) {
                arr[j] = arr[j - h];
                j = j - h;
            }
            arr[j] = x;
        }
        h = h / 2;
    }
    return arr;
}
void shellstring2(vector<string> &strings) //pivot is first value
{
    typedef vector<string>::size_type size_type;
    int h = strings.size() / 2;
    string x;
    int j;
    while (h < strings.size()) {
        h = 3 * h + 1;
    }
    while (h > 0) {
        for (size_type i = h; i < strings.size(); i++) {
            x = strings[i];
            j = i;
            while (j >= h && x < strings[j - h]) {
                strings[j] = strings[j - h];
                j = j - h;
            }
            strings[j] = x;
        }
        h = h / 2;
    }

}


void insertion_qs(int arr[], int l, int r)
{

    int x = 0;
    int j = 0;
    for (int i = l + 1; i < r; i++) {
        x = arr[i];
        j = i - 1;
        while (j >= 0 && x < arr[j]) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = x;
    }
}
void insertion_qsstring(vector<string> &strings, int l, int r)
{
    typedef vector<string>::size_type size_type;
    string x = "0";
    int j = 0;
    for (size_type i = l + 1; i < r; i++) {
        x = strings[i];
        j = i - 1;
        while (j >= 0 && x < strings[j]) {
            strings[j + 1] = strings[j];
            j = j - 1;
        }
        strings[j + 1] = x;
    }
}



void quicksort1(int arr[], int sizearr, int l, int r) //pivot is first element
{
    if (l < r) {
        int pivot = 0;
        int s = l;
        if (l < r) {
            pivot = arr[l];
            s = l;
            for (int i = l; i < r + 1; i++) {
                if (arr[i] < pivot) {
                    s++;
                    swap(arr[s], arr[i]);
                }
            }
            swap(arr[l], arr[s]);
            quicksort1(arr, sizearr, l, s - 1);
            quicksort1(arr, sizearr, s + 1, r);
        }
    }

}
void quicksort1string(vector<string> &strings, int l, int r) //pivot is first element
{
    typedef vector<string>::size_type size_type;
    if (l < r) {
        string pivot = "0";
        int s = l;
        if (l < r) {
            pivot = strings[l];
            s = l;
            for (int i = l; i < r + 1; i++) {
                if (strings[i] < pivot) {
                    s++;
                    swap(strings[s], strings[i]);
                }
            }
            swap(strings[l], strings[s]);
            quicksort1string(strings, l, s - 1);
            quicksort1string(strings, s + 1, r);
        }
    }

}

void quicksort2(int arr[], int sizearr, int l, int r) //pivot is a random element
{

    int randn = rand() % sizearr;
    swap(arr[randn], arr[0]);
    if (l < r) {
        int pivot = arr[0];
        int s = l;
        if (l < r) {
            pivot = arr[0];
            s = l;
            for (int i = l; i < r; i++) {
                if (arr[i] < pivot) {
                    s++;
                    swap(arr[s], arr[i]);
                }
            }
            swap(arr[l], arr[s]);
            quicksort1(arr, sizearr, l, s - 1);
            quicksort1(arr, sizearr, s + 1, r);
        }
    }

}
void quicksort2string(vector<string> &strings, int l, int r) //pivot is first element
{
    typedef vector<string>::size_type size_type;
    if (l < r) {
        string pivot;
        int randn = rand() % strings.size();
        swap(strings[randn], strings[0]);
        int s = l;
        if (l < r) {
            pivot = strings[0];
            s = l;
            for (size_type i = l; i < r + 1; i++) {
                if (strings[i] < pivot) {
                    s++;
                    swap(strings[s], strings[i]);
                }
            }
            swap(strings[l], strings[s]);
            quicksort2string(strings, l, s - 1);
            quicksort2string(strings, s + 1, r);
        }
    }

}

void quicksort3(int arr[], int sizearr, int l, int r) //pivot is the median
{
    random_device rd;// obtain a random number from hardware
    mt19937 eng(rd()); // seed the generator
    uniform_int_distribution<> distr(0, sizearr - 1);
    int rand1 = distr(eng);
    int rand2 = distr(eng);
    int rand3 = distr(eng);
    int median = 0;
    if (arr[rand1] <= arr[rand2] && arr[rand2] <= arr[rand3])
        median = rand2;
    if (arr[rand2] <= arr[rand1] && arr[rand1] <= arr[rand3])
        median = rand1;
    if (arr[rand1] <= arr[rand3] && arr[rand3] <= arr[rand2])
        median = rand3;
    swap(arr[median], arr[0]);
    if (l < r) {
        int pivot = arr[0];
        int s = l;
        if (l < r) {
            pivot = arr[0];
            s = l;
            for (int i = l; i <= r; i++) {
                if (arr[i] < pivot) {
                    s++;
                    swap(arr[s], arr[i]);
                }
            }
            swap(arr[l], arr[s]);
            quicksort1(arr, sizearr, l, s - 1);
            quicksort1(arr, sizearr, s + 1, r);
        }
    }

}
void quicksort3string(vector<string> &strings, int l, int r) //pivot is first element
{
    typedef vector<string>::size_type size_type;
    if (l < r) {
        string pivot = "0";
        random_device rd;// obtain a random number from hardware
        mt19937 eng(rd()); // seed the generator
        uniform_int_distribution<> distr(0, strings.size() - 1);
        int rand1 = distr(eng);
        int rand2 = distr(eng);
        int rand3 = distr(eng);
        int median = 0;
        if (strings[rand1] <= strings[rand2] && strings[rand2] <= strings[rand3])
            median = rand2;
        if (strings[rand2] <= strings[rand1] && strings[rand1] <= strings[rand3])
            median = rand1;
        if (strings[rand1] <= strings[rand3] && strings[rand3] <= strings[rand2])
            median = rand3;
        swap(strings[median], strings[0]);
        int s = l;
        if (l < r) {
            pivot = strings[0];
            s = l;
            for (size_type i = l; i < r + 1; i++) {
                if (strings[i] < pivot) {
                    s++;
                    swap(strings[s], strings[i]);
                }
            }
            swap(strings[l], strings[s]);
            quicksort3string(strings, l, s - 1);
            quicksort3string(strings, s + 1, r);
        }
    }

}

void quicksortinsert(int arr[], int sizearr, int l, int r) //pivot is first element
{
    if (l < r) {
        int pivot = 0;
        int s = l;
        if (l < r) {
            if ((r - l) < 9) {
                insertion_qs(arr, l, r);
            }
            else {
                pivot = arr[l];
                s = l;
                for (int i = l; i < r + 1; i++) {
                    if (arr[i] < pivot) {
                        s++;
                        swap(arr[s], arr[i]);
                    }
                }
                swap(arr[l], arr[s]);
                quicksortinsert(arr, sizearr, l, s - 1);
                quicksortinsert(arr, sizearr, s + 1, r);
            }
        }


    }
}
void quicksortinsertstring(vector<string> &strings, int l, int r) //pivot is first element
{
    typedef vector<string>::size_type size_type;
    if (l < r) {
        string pivot = "0";
        int s = l;
        if (l < r) {
            if ((r - l) < 9) {
                insertion_qsstring(strings, l, r);
            }
            else {
                pivot = strings[l];
                s = l;
                for (int i = l; i < r + 1; i++) {
                    if (strings[i] < pivot) {
                        s++;
                        swap(strings[s], strings[i]);
                    }
                }
                swap(strings[l], strings[s]);
                quicksortinsertstring(strings,  l, s - 1);
                quicksortinsertstring(strings,  s + 1, r);
            }
        }


    }
}


int check_if_sorted(int arr[], int sizearr) {
    int i = 1;
    int is_sorted = 1;
    while ((i < sizearr) && is_sorted)
    {
        if (arr[i - 1] > arr[i])
            is_sorted = 0;
        i++;
    }
    return is_sorted;
}
int check_if_sortedstring(vector<string> &strings) {
    int i = 1;
    int is_sorted = 1;
    while ((i < strings.size()) && is_sorted)
    {
        if (strings[i - 1] > strings[i]) {
            is_sorted = 0;
            cout << i << endl;
        }
        i++;
    }

    return is_sorted;
}

int main()
{
    const int size = 8000;
    auto rng = default_random_engine{};
    //int* array=new int[size];
    int array[size];
    for (int i = 0; i < size; i++) {
        array[i] = i + 1;
    }
    random_shuffle(&array[0], &array[size]);

    vector<string> stringlist;
    vector<double> exectimes;
    ifstream fin("words32000.txt");
    while (true) {
        string s;
        getline(fin, s);
        if (fin.eof()) {
            break;
        }
        stringlist.push_back(s);
    }
    fin.close();


    //OUTPUT SORTED TO FILE, PICK ONE METHOD
    //selectionstring(stringlist);
    //insertionstring(stringlist);
    //insertionstring2(stringlist);
    //bubblestring(stringlist);
    //bubblestring2(stringlist);
    //bubblestring3(stringlist);
    //shuffle(begin(stringlist), end(stringlist), rng);
    //ofstream fout("output1024000.txt");
    //copy(stringlist.begin(), stringlist.end(), ostream_iterator<string>(fout, "\n"));
    //fout.close();
    //cout << "completed randomizing" << endl;


    //random_shuffle(&array[0], &array[size]);
    ////SELECTION SORT
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto start = chrono::high_resolution_clock::now();
    //int *arr_sorted_selection = selection_sort(array, size);
    //auto finish = chrono::high_resolution_clock::now();
    //cout << "selection sorted?: " << check_if_sorted(arr_sorted_selection, size) << endl;
    //chrono::duration<double> elapsed = finish - start;
    //cout << "selection sort elapsed time: " << elapsed.count() << " s\n" << endl;

    //random_shuffle(&array[0], &array[size]);
    ////BUBBLE SORT
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startb = chrono::high_resolution_clock::now();
    //int *arr_sorted_bubble = bubble_sort(array, size);
    //auto finishb = chrono::high_resolution_clock::now();
    //cout << "bubble sorted?: " << check_if_sorted(arr_sorted_bubble, size) << endl;
    //chrono::duration<double> elapsedb = finishb - startb;
    //cout << "bubble sort elapsed time: " << elapsedb.count() << " s\n" << endl;

    //random_shuffle(&array[0], &array[size]);
    ////INSERTION SORT
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startc = chrono::high_resolution_clock::now();
    //int *arr_sorted_insertion = insertion_sort(array, size);
    //auto finishc = chrono::high_resolution_clock::now();
    //cout << "insertion sorted?: " << check_if_sorted(arr_sorted_insertion, size) << endl;
    //chrono::duration<double> elapsedc = finishc - startc;
    //cout << "insertion sort elapsed time: " << elapsedc.count() << " s\n" << endl;

    ////INSERTION SORT 2 (guard)
    //random_shuffle(&array[0], &array[size]);
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startd = chrono::high_resolution_clock::now();
    //int *arr_sorted_insertion2 = insertion_sort2(array, size);
    //auto finishd = chrono::high_resolution_clock::now();
    //cout << "insertion2 sorted?: " << check_if_sorted(arr_sorted_insertion2, size) << endl;
    //chrono::duration<double> elapsedd = finishd - startd;
    //cout << "insertion sort guard elapsed time: " << elapsedd.count() << " s\n" << endl;

    //random_shuffle(&array[0], &array[size]);
    ////BUBBLE SORT 2 (check if any changes were made)
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startb2 = chrono::high_resolution_clock::now();
    //int *arr_sorted_bubble2 = bubble_sort2(array, size);
    //auto finishb2 = chrono::high_resolution_clock::now();
    //cout << "bubble2 sorted?: " << check_if_sorted(arr_sorted_bubble2, size) << endl;
    //chrono::duration<double> elapsedb2 = finishb2 - startb2;
    //cout << "bubble2 sort elapsed time: " << elapsedb2.count() << " s\n" << endl;

    //random_shuffle(&array[0], &array[size]);
    ////BUBBLE SORT 3 (doesn't check the already sorted elements)
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startb3 = chrono::high_resolution_clock::now();
    //int *arr_sorted_bubble3 = bubble_sort3(array, size);
    //auto finishb3 = chrono::high_resolution_clock::now();
    //cout << "bubble3 sorted?: " << check_if_sorted(arr_sorted_bubble3, size) << endl;
    //chrono::duration<double> elapsedb3 = finishb3 - startb3;
    //cout << "bubble3 sort elapsed time: " << elapsedb3.count() << " s\n" << endl;

    ////SELECTION STRING SORT
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startss = chrono::high_resolution_clock::now();
    //selectionstring(stringlist);
    //auto finishss = chrono::high_resolution_clock::now();
    //cout << "selection string sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedss = finishss - startss;
    //cout << "selection string sort elapsed time: " << elapsedss.count() << " s\n" << endl;

    ////INSERTION STRING SORT
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startis = chrono::high_resolution_clock::now();
    //insertionstring(stringlist);
    //auto finishis = chrono::high_resolution_clock::now();
    //cout << "insertion string sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedis = finishis - startis;
    //cout << "insertion string elapsed time: " << elapsedis.count() << " s\n" << endl;

    ////INSERTION STRING2 SORT
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startis2 = chrono::high_resolution_clock::now();
    //insertionstring2(stringlist);
    //auto finishis2 = chrono::high_resolution_clock::now();
    //cout << "insertion string 2 sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedis2 = finishis2 - startis2;
    //cout << "insertion string 2 elapsed time: " << elapsedis2.count() << " s\n" << endl;

    ////BUBBLE STRING SORT
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startbs = chrono::high_resolution_clock::now();
    //bubblestring(stringlist);
    //auto finishbs = chrono::high_resolution_clock::now();
    //cout << "bubble string sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedbs = finishbs - startbs;
    //cout << "bubble string elapsed time: " << elapsedbs.count() << " s\n" << endl;

    ////BUBBLE STRING2 SORT
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startbs2 = chrono::high_resolution_clock::now();
    //bubblestring2(stringlist);
    //auto finishbs2 = chrono::high_resolution_clock::now();
    //cout << "bubble string 2 sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedbs2 = finishbs2 - startbs2;
    //cout << "bubble string 2 elapsed time: " << elapsedbs2.count() << " s\n" << endl;

    ////BUBBLE STRING3 SORT (doesn't check the already sorted elements)
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startbs3 = chrono::high_resolution_clock::now();
    //bubblestring3(stringlist);
    //auto finishbs3 = chrono::high_resolution_clock::now();
    //cout << "bubble string 3 sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedbs3 = finishbs3 - startbs3;
    //cout << "bubble string 3 elapsed time: " << elapsedbs3.count() << " s\n" << endl;




    ////QS1 SORT
    //random_shuffle(&array[0], &array[size]);
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startqs1 = chrono::high_resolution_clock::now();
    //quicksort1(array, size, 0, size - 1);
    //auto finishqs1 = chrono::high_resolution_clock::now();
    //cout << "qs1 sorted?: " << check_if_sorted(array, size) << endl;
    //chrono::duration<double> elapsedqs1 = finishqs1 - startqs1;
    //cout << "qs1 sort elapsed time: " << elapsedqs1.count() << " s\n" << endl;


    ////QS2 SORT
    //random_shuffle(&array[0], &array[size]);
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startqs2 = chrono::high_resolution_clock::now();
    //quicksort2(array, size, 0, size - 1);
    //auto finishqs2 = chrono::high_resolution_clock::now();
    //cout << "qs2 sorted?: " << check_if_sorted(array, size) << endl;
    //chrono::duration<double> elapsedqs2 = finishqs2 - startqs2;
    //cout << "qs2 sort elapsed time: " << elapsedqs2.count() << " s\n" << endl;


    ////QS3 SORT
    //random_shuffle(&array[0], &array[size]);
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startqs3 = chrono::high_resolution_clock::now();
    //quicksort3(array, size, 0, size - 1);
    //auto finishqs3 = chrono::high_resolution_clock::now();
    //cout << "qs3 sorted?: " << check_if_sorted(array, size) << endl;
    //chrono::duration<double> elapsedqs3 = finishqs3 - startqs3;
    //cout << "qs3 sort elapsed time: " << elapsedqs3.count() << " s\n" << endl;

    ////QSINSERT SORT
    //random_shuffle(&array[0], &array[size]);
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startqs4 = chrono::high_resolution_clock::now();
    //quicksortinsert(array, size, 0, size - 1);
    //auto finishqs4 = chrono::high_resolution_clock::now();
    //cout << "qs+insertion sorted?: " << check_if_sorted(array, size) << endl;
    //chrono::duration<double> elapsedqs4 = finishqs4 - startqs4;
    //cout << "qs+insertion sort elapsed time: " << elapsedqs4.count() << " s\n" << endl;

    ////SHELL1 SORT
    //random_shuffle(&array[0], &array[size]);
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startsh1 = chrono::high_resolution_clock::now();
    //int *arr_sorted_shell1 = shell1(array, size);
    //auto finishsh1 = chrono::high_resolution_clock::now();
    //cout << "shell1 sorted?: " << check_if_sorted(arr_sorted_shell1, size) << endl;
    //chrono::duration<double> elapsedsh1 = finishsh1 - startsh1;
    //cout << "shell1 sort elapsed time: " << elapsedsh1.count() << " s\n" << endl;



    ////SHELL2 SORT
    //random_shuffle(&array[0], &array[size]);
    //cout << "random sorted?: " << check_if_sorted(array, size) << endl;
    //auto startsh2 = chrono::high_resolution_clock::now();
    //int *arr_sorted_shell2 = shell2(array, size);
    //auto finishsh2 = chrono::high_resolution_clock::now();
    //cout << "shell2 sorted?: " << check_if_sorted(arr_sorted_shell2, size) << endl;
    //chrono::duration<double> elapsedsh2 = finishsh2 - startsh2;
    //cout << "shell2 sort elapsed time: " << elapsedsh2.count() << " s\n" << endl;

    ////SHELL1 STRING SORT
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startsh1s = chrono::high_resolution_clock::now();
    //shellstring(stringlist);
    //auto finishsh1s = chrono::high_resolution_clock::now();
    //cout << "shell1 string sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedsh1s = finishsh1s - startsh1s;
    //cout << "shell1 string elapsed time: " << elapsedsh1s.count() << " s\n" << endl;

    ////SHELL2 STRING SORT
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startsh2s = chrono::high_resolution_clock::now();
    //shellstring2(stringlist);
    //auto finishsh2s = chrono::high_resolution_clock::now();
    //cout << "shell2 string sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedsh2s = finishsh2s - startsh2s;
    //cout << "shell2 string elapsed time: " << elapsedsh2s.count() << " s\n" << endl;

    //QS1 STRING SORT
    shuffle(begin(stringlist), end(stringlist), rng);
    cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    auto startqs1s = chrono::high_resolution_clock::now();
    quicksort1string(stringlist, 0, stringlist.size() - 1);
    auto finishqs1s = chrono::high_resolution_clock::now();
    cout << "QS1 string sorted?: " << check_if_sortedstring(stringlist) << endl;
    chrono::duration<double> elapsedqs1s = finishqs1s - startqs1s;
    cout << "QS1 string elapsed time: " << elapsedqs1s.count() << " s\n" << endl;

    //QS2 STRING SORT
    shuffle(begin(stringlist), end(stringlist), rng);
    cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    auto startqs2s = chrono::high_resolution_clock::now();
    quicksort2string(stringlist, 0, stringlist.size() - 1);
    auto finishqs2s = chrono::high_resolution_clock::now();
    cout << "QS2 string sorted?: " << check_if_sortedstring(stringlist) << endl;
    chrono::duration<double> elapsedqs2s = finishqs2s - startqs2s;
    cout << "QS2 string elapsed time: " << elapsedqs2s.count() << " s\n" << endl;

    ////QS3 STRING SORT
    //shuffle(begin(stringlist), end(stringlist), rng);
    //cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    //auto startqs3s = chrono::high_resolution_clock::now();
    //quicksort3string(stringlist, 0, stringlist.size() - 1);
    //auto finishqs3s = chrono::high_resolution_clock::now();
    //cout << "QS3 string sorted?: " << check_if_sortedstring(stringlist) << endl;
    //chrono::duration<double> elapsedqs3s = finishqs3s - startqs3s;
    //cout << "QS3 string elapsed time: " << elapsedqs3s.count() << " s\n" << endl;

    //QS+INSERT STRING SORT
    shuffle(begin(stringlist), end(stringlist), rng);
    cout << "randomly sorted?: " << check_if_sortedstring(stringlist) << endl;
    auto startqs4s = chrono::high_resolution_clock::now();
    quicksortinsertstring(stringlist, 0, stringlist.size() - 1);
    auto finishqs4s = chrono::high_resolution_clock::now();
    cout << "QS + insert string sorted?: " << check_if_sortedstring(stringlist) << endl;
    chrono::duration<double> elapsedqs4s = finishqs4s - startqs4s;
    cout << "QS + insert string elapsed time: " << elapsedqs4s.count() << " s\n" << endl;



//  exectimes.push_back(elapsedqs1s.count());
//  exectimes.push_back(elapsedqs2s.count());
//  exectimes.push_back(elapsedqs3s.count());
//  exectimes.push_back(elapsedqs4s.count());
//  exectimes.push_back(elapsedsh1s.count());
//  exectimes.push_back(elapsedsh2s.count());


    vector<string> doubleStr;
    transform(exectimes.begin(),
        exectimes.end(),
        back_inserter(doubleStr),
        [](double d) { return to_string(d); }
    );

    //ofstream fout("times.txt");
    //copy(timesstr.begin(), timesstr.end(), ostream_iterator<string>(fout, "\n"));
    //fout.close();

    ofstream output_file("times.txt");
    ostream_iterator<string> output_iterator(output_file, "\n");
    copy(doubleStr.begin(), doubleStr.end(), output_iterator);
    output_file.close();
    system("pause");

    return 0;
}