//in this project we compare those 3 algorithms for sorting in all 3 cases:average, best and worst.The best case for
//all of the algorithms the array must be sorted in ascendig order, for the worst case the array must be sorted in
//descendig order and for the average case, we will use an unsorted array.From the graphs, we observe that in the best case, bubble sort
//and selection sort have the same number of comparisons/assignments, and insertion sort has the same values in these cases.
//The complexity of bubble sort for the best case is O(n), and for the average/worst case is O(n^2), insertion sort in the best case has the complexity O(n), and in
//the /averageworst case is O(n^2), and selection sort has the complexity O(n^2) for all cases.
#include <iostream>
#include "Profiler.h"

#define AVG_BUBBLE_COMP "avg_bubble_comp"
#define AVG_BUBBLE_ASSIG "avg_bubble_assig"
#define AVG_BUBBLE_OP "avg_bubble_operations"
#define AVG_INSERTION_OP "avg_insertion_operations"

#define AVG_SELECTION_COMP "avg_selection_comp"
#define AVG_SELECTION_ASSIG "avg_selection_assig"
#define AVG_SELECTION_OP "avg_selection_operations"

#define AVG_INSERTION_COMP "avg_insertion_comp"
#define AVG_INSERTION_ASSIG "avg_insertion_assig"
#define AVG_INSERTION_OP "avg_insertion_op"

#define BEST_BUBBLE_COMP "best_bubble_comp"
#define BEST_BUBBLE_ASSIG "best_bubble_assig"
#define BEST_BUBBLE_OP "best_bubble_op"

#define BEST_INSERTION_COMP "best_insertion_comp"
#define BEST_INSERTION_ASSIG "best_insertion_assig"
#define BEST_INSERTION_OP "best_insertion_op"

#define BEST_SELECTION_COMP "best_selection_comp"
#define BEST_SELECTION_ASSIG "best_selection_assig"
#define BEST_SELECTION_OP "best_selection_op"

#define WORST_BUBBLE_COMP "worst_bubble_comp"
#define WORST_BUBBLE_ASSIG "worst_bubble_assig"
#define WORST_BUBBLE_OP "worst_bubble_op"

#define WORST_SELECTION_COMP "worst_selection_comp"
#define WORST_SELECTION_ASSIG "worst_selection_assig"
#define WORST_SELECTION_OP "worst_selection_op"

#define WORST_INSERTION_COMP "worst_insertion_comp"
#define WORST_INSERTION_ASSIG "worst_insertion_assig"
#define WORST_INSERTION_OP "worst_insertion_op"

using namespace std;
Profiler profiler("sort");

int comp_bubble, comp_insert, comp_sel, assig_bubble, assig_insert, assig_sel, op_bubble, op_insert, op_sel;
void printArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << "\n";

}
void bubbleSort(int* a, int n)
{
	assig_bubble = 0;
	comp_bubble = 0;
	int i, j, aux;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				aux = a[j];
				a[j] = a[j + 1];
				a[j + 1] = aux;
				assig_bubble += 3;
			}
			comp_bubble++;
		}
	}
}
void selectionSort(int* a, int n)
{
	assig_sel = 0;
	comp_sel = 0;
	int buff, aux;
	for (int i = 0; i < n - 1; i++)//we go until n-1 because the last element is the biggest element from the array
	{
		buff = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[buff] > a[j])
				buff = j;
			comp_sel++;
			//here we find the minimum element from the unsorted array
		}
		if (buff != i)
			//here we compare if we changed the index earlier, and if yes, that means
			//that we found a smaller number than the number on the position i, and we swap them
		{
			aux = a[buff];
			a[buff] = a[i];
			a[i] = aux;
			assig_sel += 3;
		}

	}
}
void insertionSort(int* a, int n)
{
	assig_insert = 0;
	comp_insert = 0;
	int buff, j;
	for (int i = 1; i < n; i++)
	{
		buff = a[i];
		assig_insert++;
		j = i - 1;
		while (j >= 0 && buff < a[j])
		{
			//we shift to the right the element which is bigger than buff
			a[j + 1] = a[j];
			assig_insert++;
			j--;
		}
		if (j>=0)
		comp_insert++;
		a[j+1] = buff;
		assig_insert++;
	}

}
void demoBubble()
{
	cout << "Demo Bubble" << "\n";
	int a[5] = { 9,3,7,11,12 };
	bubbleSort(a, 5);
	printArray(a, 5);
}
void demoSelection()
{
	cout << "\n" << "Demo Selection" << "\n";
	int a[5] = { 9,3,7,11,12 };
	selectionSort(a, 5);
	printArray(a, 5);
}
void demoInsertion()
{
	int n = 5;
	cout << "\n" << "Demo Insertion" << "\n";
	int a[5] = { 9,3,7,11,12 };
	insertionSort(a, n);
	printArray(a, n);

}
int* generateAvgCase(int n)
{
	int* a = (int*)malloc(n * sizeof(int));
	FillRandomArray(a, n);
	return a;
}
int* generateAscendingOrder(int n)
{
	int* a = (int*)malloc(n * sizeof(int));
	FillRandomArray(a, n, 10, 5000, false, 1); //array, size of the array, the interval of possible values, unique(not specified), sorted in ascending order
	return a;
}
int* generateDescendingOreder(int n)
{
	int* a = (int*)malloc(n * sizeof(int));
	FillRandomArray(a, n, 10, 5000, false, 2);//array, size of the array, the interval of possible values, unique(not specified), sorted in descending order
	return a;
}

void generateGraphs()
{
	for (int size = 100; size <= 10000; size += 100)
	{
		///average cases
		int* a = generateAvgCase(size);
		int* b = (int*)malloc(size * sizeof(int));
		for (int i = 0; i < size; i++)
			b[i] = a[i];
		//for the avg cases we have to use the same values, so we create a copy of a in b
		bubbleSort(b, size);
		profiler.countOperation(AVG_BUBBLE_COMP, size, comp_bubble);
		profiler.countOperation(AVG_BUBBLE_ASSIG, size, assig_bubble);
		profiler.addSeries(AVG_BUBBLE_OP, AVG_BUBBLE_COMP, AVG_BUBBLE_ASSIG);

		for (int i = 0; i < size; i++)
			b[i] = a[i];
		selectionSort(b, size);
		profiler.countOperation(AVG_SELECTION_COMP, size, comp_sel);
		profiler.countOperation(AVG_SELECTION_ASSIG, size, assig_sel);//we create a separate graph because it can not be seen on the main graph
		profiler.addSeries(AVG_SELECTION_OP, AVG_SELECTION_COMP, AVG_SELECTION_ASSIG);

		for (int i = 0; i < size; i++)
			b[i] = a[i];
		insertionSort(b, size);
		profiler.countOperation(AVG_INSERTION_COMP, size, comp_insert);//we create a separate graph because it can not be seen on the main graph
		profiler.countOperation(AVG_INSERTION_ASSIG, size, assig_insert);
		profiler.addSeries(AVG_INSERTION_OP, AVG_INSERTION_COMP, AVG_INSERTION_ASSIG);
		free(b);
		///best cases
		a = generateAscendingOrder(size);
		bubbleSort(a, size);
		profiler.countOperation(BEST_BUBBLE_COMP, size, comp_bubble);
		profiler.countOperation(BEST_BUBBLE_ASSIG, size, assig_bubble);
		profiler.addSeries(BEST_BUBBLE_OP, BEST_BUBBLE_COMP, BEST_BUBBLE_ASSIG);
		free(a);

		a = generateAscendingOrder(size);
		selectionSort(a, size);
		profiler.countOperation(BEST_SELECTION_COMP, size, comp_sel);
		profiler.countOperation(BEST_SELECTION_ASSIG, size, assig_sel);
		profiler.addSeries(BEST_SELECTION_OP, BEST_SELECTION_COMP, BEST_SELECTION_ASSIG);
		free(a);

		a = generateAscendingOrder(size);
		insertionSort(a, size);
		profiler.countOperation(BEST_INSERTION_COMP, size, comp_insert);//we create a separate graph because it can not be seen on the main graph
		profiler.countOperation(BEST_INSERTION_ASSIG, size, assig_insert);
		profiler.addSeries(BEST_INSERTION_OP, BEST_INSERTION_COMP, BEST_INSERTION_ASSIG);//we create a separate graph because it can not be seen on the main graph
		free(a);
		///worst cases
		a = generateDescendingOreder(size);
		bubbleSort(a, size);
		profiler.countOperation(WORST_BUBBLE_COMP, size, comp_bubble);
		profiler.countOperation(WORST_BUBBLE_ASSIG, size, assig_bubble);
		profiler.addSeries(WORST_BUBBLE_OP, WORST_BUBBLE_COMP, WORST_BUBBLE_ASSIG);
		free(a);

		a = generateDescendingOreder(size);
		selectionSort(a, size);
		profiler.countOperation(WORST_SELECTION_COMP, size, comp_sel);
		profiler.countOperation(WORST_SELECTION_ASSIG, size, assig_sel);//we create a separate graph because it can not be seen on the main graph
		profiler.addSeries(WORST_SELECTION_OP, WORST_SELECTION_COMP, WORST_SELECTION_ASSIG);
		free(a);

		a = generateDescendingOreder(size);
		insertionSort(a, size);
		profiler.countOperation(WORST_INSERTION_COMP, size, comp_insert);//we create a separate graph because it can not be seen on the main graph
		profiler.countOperation(WORST_INSERTION_ASSIG, size, assig_insert);
		profiler.addSeries(WORST_INSERTION_OP, WORST_INSERTION_COMP, WORST_INSERTION_ASSIG);
		free(a);

		profiler.createGroup("Average Case Comp", AVG_BUBBLE_COMP, AVG_SELECTION_COMP);
		profiler.createGroup("Average Case Assig", AVG_BUBBLE_ASSIG, AVG_INSERTION_ASSIG);
		profiler.createGroup("Average Case Op", AVG_BUBBLE_OP, AVG_SELECTION_OP, AVG_INSERTION_OP);

		profiler.createGroup("Best Case Comp", BEST_BUBBLE_COMP, BEST_SELECTION_COMP);
		profiler.createGroup("Best Case Assig", BEST_BUBBLE_ASSIG, BEST_SELECTION_ASSIG, BEST_INSERTION_ASSIG);
		profiler.createGroup("Best Case Op", BEST_BUBBLE_OP, BEST_SELECTION_OP);

		profiler.createGroup("Worst Case Comp", WORST_BUBBLE_COMP, WORST_SELECTION_COMP);
		profiler.createGroup("Worst Case Assig", WORST_BUBBLE_ASSIG, WORST_INSERTION_ASSIG);
		profiler.createGroup("Worst Case Op", WORST_BUBBLE_OP, WORST_SELECTION_OP, WORST_INSERTION_OP);

	}
}
int main()
{
	demoBubble();
	demoInsertion();
	demoSelection();
	generateGraphs();
	profiler.showReport();

	return 0;
}