//Keith Perkins
//CS 2420
//Program 6
//Sorting
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <time.h>
#include <stdio.h>
#include <dos.h>
#include "stdafx.h"
using namespace std;

void insertionSort(int a[], int l);
void shellSort(int a[], int l);
void quickSort(int a[], int start, int end);
int main()
{
	clock_t clock();
	clock_t start;
	clock_t end;
	clock_t elapsed_clock;
	clock_t elapsed_time;
	string fileName1 = "file1.txt";
	string fileName2 = "file2.txt";
	string fileName3 = "file3.txt";
	vector<int> file1vec;
	vector<int> file2vec;
	vector<int> file3vec;
	int count1 = 0;
	int count2 = 0;
	int count3 = 0;
	//1.	Read in file1 from the download area containing integers in text format
	ifstream iDataFile;
	iDataFile.open(fileName1);
	if (iDataFile.fail())
	{
		cout << "Invalid file 1." << endl;
		system("PAUSE");
		return 1;
	}
	//2.	Count the number of elements in the file
	while (!(iDataFile.eof()))
	{
		int data;
		iDataFile >> data;
		file1vec.push_back(data);
		count1++;
	}
	int* file1arr = new int[count1];
	for (int i = 0; i < count1; i++)
	{
		file1arr[i] = file1vec.at(i);
	}
	iDataFile.close();
	iDataFile.open(fileName2);
	if (iDataFile.fail())
	{
		cout << "Invalid file 2." << endl;
		system("PAUSE");
		return 1;
	}
	while (!(iDataFile.eof()))
	{
		int data;
		iDataFile >> data;
		file2vec.push_back(data);
		count2++;
	}
	int* file2arr = new int[count2];
	for (int i = 0; i < count2; i++)
	{
		file2arr[i] = file2vec.at(i);
	}
	iDataFile.close();
	iDataFile.open(fileName3);
	if (iDataFile.fail())
	{
		cout << "Invalid file 3." << endl;
		system("PAUSE");
		return 1;
	}
	while (!(iDataFile.eof()))
	{
		int data;
		iDataFile >> data;
		file3vec.push_back(data);
		count3++;
	}
	int* file3arr = new int[count3];
	for (int i = 0; i < count3; i++)
	{
		file3arr[i] = file3vec.at(i);
	}

	start = clock();
	insertionSort(file1arr, count1);
	end = clock();
	elapsed_clock = end - start;
	elapsed_time = ((end - start) / CLK_TCK);
	cout << "The elapsed clock was: " << elapsed_clock << endl;
	cout << "The elapsed time was:  " << elapsed_time << endl;
	ofstream oDataFile;
	oDataFile.open("I1.txt");
	for (int i = 0; i < count1; i++)
		oDataFile << file1arr[i] << endl;
	oDataFile.close();

	start = clock();
	shellSort(file1arr, count1);
	end = clock();
	elapsed_clock = end - start;
	elapsed_time = ((end - start) / CLK_TCK);
	cout << "The elapsed clock was: " << elapsed_clock << endl;
	cout << "The elapsed time was:  " << elapsed_time << endl;
	oDataFile.open("S1.txt");
	for (int i = 0; i < count1; i++)
		oDataFile << file1arr[i] << endl;
	oDataFile.close();

	start = clock();
	quickSort(file1arr, 0, count1);
	end = clock();
	elapsed_clock = end - start;
	elapsed_time = ((end - start) / CLK_TCK);
	cout << "The elapsed clock was: " << elapsed_clock << endl;
	cout << "The elapsed time was:  " << elapsed_time << endl;
	oDataFile.open("Q1.txt");
	for (int i = 0; i < count1; i++)
		oDataFile << file1arr[i] << endl;
	oDataFile.close();

	start = clock();
	insertionSort(file2arr, count2);
	end = clock();
	elapsed_clock = end - start;
	elapsed_time = ((end - start) / CLK_TCK);
	cout << "The elapsed clock was: " << elapsed_clock << endl;
	cout << "The elapsed time was:  " << elapsed_time << endl;
	oDataFile.open("I2.txt");
	for (int i = 0; i < count2; i++)
		oDataFile << file2arr[i] << endl;
	oDataFile.close();

	start = clock();
	shellSort(file2arr, count2);
	end = clock();
	elapsed_clock = end - start;
	elapsed_time = ((end - start) / CLK_TCK);
	cout << "The elapsed clock was: " << elapsed_clock << endl;
	cout << "The elapsed time was:  " << elapsed_time << endl;
	oDataFile.open("S2.txt");
	for (int i = 0; i < count2; i++)
		oDataFile << file2arr[i] << endl;
	oDataFile.close();

	start = clock();
	quickSort(file2arr, 0, count2);
	end = clock();
	elapsed_clock = end - start;
	elapsed_time = ((end - start) / CLK_TCK);
	cout << "The elapsed clock was: " << elapsed_clock << endl;
	cout << "The elapsed time was:  " << elapsed_time << endl;
	oDataFile.open("Q2.txt");
	for (int i = 0; i < count2; i++)
		oDataFile << file2arr[i] << endl;
	oDataFile.close();

	//3.	Obtain the starting clock tick value for the Insertion Sort
	//4.	Sort the file with the Insertion Sort
	//5.	Obtain the ending clock tick value for the Insertion Sort
	//6.	Obtain the starting clock tick value for the Shellsort
	//7.	Sort the file with the Shellsort
	//8.	Obtain the ending clock tick value for the Shellsort
	//9.	Obtain the starting clock tick value for the Quicksort
	//10.	Sort the file with the Quicksort
	//11.	Obtain the ending clock tick value for the Quicksort
	//12.	Display the statistical information for the file for each sort(see example below).
	//13.	Write the sorted file out to the disk with a new name with the first letter of the sort(i.e.I for the Insertion sort, S for the Shellsort, or Q for the Quicksort) followed by the number of the file(i.e.I1, I2, I3 for the Insertion Sorted files, S1, S2, S3 for the Shellsort, and Q1, Q2, Q3 for the Quicksort).Each number should be written as text with each number on a separate line in the file.
	//14.	Repeat these steps for file2 and file3
	system("PAUSE");
	return 0;
}

void insertionSort(int a[], int l)
{
	int j = 0;
	int temp;

	for (int i = 1; i < l; i++)
	{
		j = i;

		while (j > 0 && a[j] < a[j - 1])
		{
			temp = a[j];
			a[j] = a[j - 1];
			a[j - 1] = temp;
			j--;
		}
	}
}

//void shellsort(int a[], int l)
//{
//	int gap, i, j, temp;
//	for (gap = l / 2; gap > 0; gap /= 2)
//	{
//		for (i = gap; i < l; i++)
//		{
//			for (j = i - gap; j >= 0 && a[j]>a[j + gap]; j -= gap)
//			{
//				temp = a[j];
//				a[j] = a[j + gap];
//				a[j + gap] = temp;
//			}
//		}
//	}
//}

void shellSort(int v[], int n)

{

	int gap, i, j, temp;



	for (gap = n / 2; gap > 0; gap /= 2)

	for (i = gap; i < n; i++)

	for (j = i - gap; j >= 0 && v[j]>v[j + gap]; j -= gap) {

		temp = v[j];

		v[j] = v[j + gap];

		v[j + gap] = temp;

	}

}

//void quickSort(int a[], int start, int end)
//{
//	int i = start, j = end;
//	int temp;
//	int pivot = a[(start + end) / 2];
//
//	while (i <= j)
//	{
//		while (a[i] < pivot)
//			i++;
//		while (a[j] > pivot)
//			j--;
//		if (i <= j)
//		{
//			temp = a[i];
//			a[i] = a[j];
//			a[j] = temp;
//			i++;
//			j--;
//		}
//	}
//	if (start < j)
//		quickSort(a, start, j);
//	if (i < end)
//		quickSort(a, i, end);
//}

void quickSort(int arr[], int left, int right)
{
	int i = left, j = right;
	int tmp;
	int pivot = arr[(left + right) / 2];

	/* partition */
	while (i <= j) {
		while (arr[i] < pivot)
			i++;
		while (arr[j] > pivot)
			j--;
		if (i <= j) {
			tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
			j--;
		}
	}
	/* recursion */
	if (left < j)
		quickSort(arr, left, j);
	if (i < right)
		quickSort(arr, i, right);
}