#include "pch.h"
#include <iostream>
#define N 100000
#include <stdlib.h>
#include <time.h>
#include <fstream>
using namespace std;
void insertion_sort(int a[], int n);
void selection_sort(int a[], int n);
void IS(int n);
void SS(int n);
double best_IS=0, worst_IS=0, avarage_IS=0,best_SS=0,worst_SS=0,avarage_SS=0;

int main()
{
	ofstream fout("lista.txt");
	srand(time(0));
	int n = 100000;
	IS(n);
	SS(n);
	return 0;
}

void insertion_sort(int a[], int n)
{
	int v;
	for (int i = 0; i <= n - 1; ++i)
	{
		for (int j = i - 1; j >= 0; --j)
		{
			if (a[j] > a[j + 1])
			{
				//swap(a[j], a[j + 1]);
				v = a[j]; a[j] = a[j + 1]; a[j + 1] = v;
			}
		}
	}
}
void selection_sort(int a[], int n)
{
	int min_idx,v;
	for (int i = 0; i < n - 1; ++i) {
		min_idx = i;
		for (int j = i + 1; j < n; ++j) {
			if (a[j] > a[min_idx]) {
				min_idx = j;
			}
		}
		v = a[i]; a[i] = a[min_idx]; a[min_idx] = v;
		// swap(a[i], a[min_idx]);
	}
}
void IS(int n) {
	int i;
	int a[N];
	clock_t start, stop;
	double best, worst, avarage, ido;
	cout << "Insertion sort.\n\nWorking with array lenght of: " << n << endl;
	cout << "Worst case generation started..." << endl;
	for (i = 0; i < n; ++i)
	{
		a[i] = n - i - 1;
	}
	cout << "Worst case generation finished, now sorting..." << endl;
	start = clock();
	insertion_sort(a, n);
	stop = clock();
	ido = stop - start;
	ido /= CLOCKS_PER_SEC;
	worst = ido;
	cout << "Finished. Time: " << worst << endl;
	cout << "\nBest case generation started..." << endl;
	for (i = 0; i < n; ++i)
	{
		a[i] = i;
	}
	cout << "Best case generation finished, now sorting..." << endl;
	start = clock();
	insertion_sort(a, n);
	stop = clock();
	ido = stop - start;
	ido /= CLOCKS_PER_SEC;
	best = ido;
	cout << "Finished. Time: " << best << endl;
	cout << "\nAvarage case generation started..." << endl;
	for (i = 0; i < n; ++i) {
		a[i] = rand() % n;
	}
	cout << "Avarage case generation finished, now sorting..." << endl;
	start = clock();
	insertion_sort(a, n);
	stop = clock();
	ido = stop - start;
	ido /= CLOCKS_PER_SEC;
	avarage = ido;
	cout << "Finished. Time: " << avarage << endl;

	cout << "\nWorst: " << worst << endl << "Best: " << best << endl << "Avarage: " << avarage << endl << endl;
	best_IS = best;
	avarage_IS = avarage;
	worst_IS = worst;
}
void SS(int n) {
	int i;
	int a[N];
	clock_t start, stop;
	double best, worst, avarage, ido;
	cout << "Selection sort.\n\nWorking with array lenght of: " << n << endl;
	cout << "Worst case generation started..." << endl;
	for (i = 0; i < n; ++i)
	{
		a[i] = n - i - 1;
	}
	cout << "Worst case generation finished, now sorting..." << endl;
	start = clock();
	selection_sort(a, n);
	stop = clock();
	ido = stop - start;
	ido /= CLOCKS_PER_SEC;
	worst = ido;
	cout << "Finished. Time: " << worst << endl;
	cout << "\nBest case generation started..." << endl;
	for (i = 0; i < n; ++i)
	{
		a[i] = i;
	}
	cout << "Best case generation finished, now sorting..." << endl;
	start = clock();
	selection_sort(a, n);
	stop = clock();
	ido = stop - start;
	ido /= CLOCKS_PER_SEC;
	best = ido;
	cout << "Finished. Time: " << best << endl;
	cout << "\nAvarage case generation started..." << endl;
	for (i = 0; i < n; ++i) {
		a[i] = rand() % n;
	}
	cout << "Avarage case generation finished, now sorting..." << endl;
	start = clock();
	selection_sort(a, n);
	stop = clock();
	ido = stop - start;
	ido /= CLOCKS_PER_SEC;
	avarage = ido;
	cout << "Finished. Time: " << avarage << endl;

	cout << "\nWorst: " << worst << endl << "Best: " << best << endl << "Avarage: " << avarage << endl<<endl;
	best_IS = best;
	avarage_IS = avarage;
	worst_IS = worst;
}