/*
	Moldovan Vlad-Madalin 30227
	S-au implementat algoritmii:
		bubble sort
		insertion sort
		selection sort
	Performanta pe cazul mediu:
		bubble sort - O(n^2)

	Observatii:
		Pe best case , bubble sort nu face nici o asignare .
		Pe average case , cel mai rapid algoritm a fost ...
		...



*/
#include<iostream>
#include "Profiler.h"

Profiler p("lab1");

using namespace std;
void afisare(int v[], int n)
{
	for (int i = 0; i < n; i++)
		cout << v[i] << " ";
	cout << endl;
}
void bubble(int v[], int n)
{
	int sorted = 0;
	int i, aux;
	Operation comp = p.createOperation("bubble_comp", n);
	Operation assign = p.createOperation("bubble_assign", n);
	while (!sorted)
	{
		sorted = 1;
		for (i = 0; i < n - 1; i++)
		{
			comp.count();
			if (v[i] > v[i + 1])
			{
				sorted = 0;
				assign.count(3);
				aux = v[i];
				v[i] = v[i + 1];
				v[i + 1] = aux;
			}
		}
	}
}
void insertionSort(int v[], int n)
{
	int i, j, aux;
	Operation comp = p.createOperation("insertion_comp", n);
	Operation assign = p.createOperation("insertion_assign", n);
	for (i = 1; i < n; i++)
	{
		aux = v[i];
		assign.count();
		j = i - 1;
		while (j >= 0 && v[j] > aux)
		{
			comp.count();
			v[j + 1] = v[j];
			j--;
		}
		v[j + 1] = aux;
		assign.count();
		if (j >= 1)
			comp.count();
	}
}
void selectionSort(int v[], int n)
{
	Operation comp = p.createOperation("selection_comp", n);
	Operation assign = p.createOperation("selection_assign", n);
	int i, j, pozmin,aux;
	for (i = 0; i < n - 1; i++)
	{
		pozmin = i;
		for (j = i + 1; j < n; j++)
		{
			comp.count();
			if (v[j] < v[pozmin])
			{
				pozmin = j;
			}
			if (pozmin != i)
			{
				assign.count(3);
				aux = v[i];
				v[i] = v[pozmin];
				v[pozmin] = aux;
			}
		}
	}

}
void demo()
{
	int v[] = { 2, -1, 5, 6, 3, 8, 4 };
	int u[100];
	int n = sizeof(v) / sizeof(v[0]);

	afisare(v, n);
	memcpy(u, v, n * sizeof(v[0]));
	bubble(u, n);
	afisare(u, n);

	afisare(v, n);
	memcpy(u, v, n * sizeof(v[0]));
	insertionSort(u, n);
	afisare(u, n);

	afisare(v, n);
	memcpy(u, v, n * sizeof(v[0]));
	selectionSort(u, n);
	afisare(u, n);

}
void perfAverage()
{
	int v[10000];
	int u[10000];
	for (int n = 100; n <= 10000; n += 100) {
		for (int test = 0; test < 5; test++) {
			FillRandomArray(v, n);
			memcpy(u, v, n * sizeof(v[0]));
			bubble(v, n);
			memcpy(u, v, n * sizeof(v[0]));
			insertionSort(u, n);
		}
		cout << n << endl;
	}
	p.addSeries("bubble", "bubble_comp", "bubble_assign");
	p.addSeries("insertion", "insertion_comp", "bubble_assign");
	p.addSeries("selection", "selection_comp", "selection_assign");
	p.createGroup("view", "bubble", "insertion","selection");
	p.createGroup("view_comp", "bubble_comp", "insertion_comp","selection_comp");
	p.createGroup("view_assign", "bubble_assign", "insertion_assign","selection_comp");
	p.showReport();
}
void perfBest()
{
	int v[10000];
	int u[10000];
	for (int n = 100; n <= 10000; n += 100) {
		FillRandomArray(v, n, 10, 50000, false, ASCENDING);
		memcpy(u, v, n * sizeof(v[0]));
		bubble(v, n);
		memcpy(u, v, n * sizeof(v[0]));
		insertionSort(u, n);
		cout << n << endl;
	}
	p.addSeries("bubble", "bubble_comp", "bubble_assign");
	p.addSeries("insertion", "insertion_comp", "bubble_assign");
	p.addSeries("selection", "selection_comp", "selection_assign");
	p.createGroup("view", "bubble", "insertion", "selection");
	p.createGroup("view_comp", "bubble_comp", "insertion_comp", "selection_comp");
	p.createGroup("view_assign", "bubble_assign", "insertion_assign", "selection_comp");
	p.showReport();
}
void perfWorst()
{
	int v[10000];
	int u[10000];
	for (int n = 100; n <= 10000; n += 100) {
		cout << n << endl;
		FillRandomArray(v, n, 10, 50000, false, DESCENDING);
		memcpy(u, v, n * sizeof(v[0]));
		bubble(v, n);
		memcpy(u, v, n * sizeof(v[0]));
		insertionSort(u, n);
	}
	p.addSeries("bubble", "bubble_comp", "bubble_assign");
	p.addSeries("insertion", "insertion_comp", "bubble_assign");
	p.createGroup("view", "bubble", "insertion");
	p.createGroup("view_comp", "bubble_comp", "insertion_comp");
	p.createGroup("view_assign", "bubble_assign", "insertion_assign");
	p.showReport();
}
int main()
{
	demo();
	/*perfAverage();
	p.reset("lab1-best");
	perfBest();
	p.reset("lab1-worst");
	perfWorst();*/

	system("pause");
	return 0;
}