#include "stdafx.h"
#include "time.h"
#include <iostream>


using namespace std;
unsigned long int const n = 20000000;

float z[n+1];

void bubble_sort(unsigned long int n, float *a)
{
	unsigned long int l, k;
	float p;
	l = n;
	do
	{
		l = l - 1; k = 0;
		for (unsigned long int i = 1; i <= l; i++)
		if (a[i] > a[i + 1])
		{
			p = a[i]; a[i] = a[i + 1]; a[i + 1] = p; k = k + 1;
		}
	} while (k != 0);
}

void sort_insert(unsigned long int n, float *a)
{

	float y, w;
	unsigned long int l, p, s, k;
	w = -1.7e38;
	a[0] = w;
	for (unsigned long int i = 2; i <= n; i++)
	{
		y = a[i]; l = 0; p = i - 1;
		do
		{
			s = (l + p + 1) / 2;
			if (a[s] <= y)l = s; else p = s - 1;
		} while (l != p);
		k = l;
		for (unsigned long int j = i - 1; j >= k + 1; j--)
			a[j + 1] = a[j];
		a[k + 1] = y;
	}
}

void scaluj(unsigned long int l, unsigned long int s, unsigned long int p, float *a)
{
	//float z[n + 1];
	unsigned long int i, j, m, k;
	i = l; j = s; m = l;
	do
	{
		if (a[i] <= a[j])
		{
			z[m] = a[i]; i = i + 1;
		}
		else { z[m] = a[j]; j = j + 1; }
		m = m + 1;
	} while (i < s && j <= p);
	if (i < s)
	{
		k = p;
		for (unsigned long int j = s - 1; j >= i; j--)
		{
			a[k] = a[j];
			k = k - 1;
		}
	}
	for (unsigned long int i = l; i <= m - 1; i++)
		a[i] = z[i];
}
void sort_scal(unsigned long int d, unsigned long int g, float *a)
{
	unsigned long int s;
	if (d < g)
	{
		s = (d + g) / 2;
		sort_scal(d, s, a);
		sort_scal(s + 1, g, a);
		scaluj(d, s + 1, g, a);
	}
}
void quick_sort(unsigned long int d, unsigned long int g, float *a)
{
	unsigned long int l, p, s;
		float v, u;
	l = d; p = g;
	s = (d + g)/2;
	v = a[s];
	do
	{
		while (a[l] < v) l = l + 1;
		while (a[p] > v) p = p - 1;
		if (l <= p)
		{
			u = a[l];
			a[l] = a[p];
			a[p] = u;
			l = l + 1; p = p - 1;
		}
	} while (l <= p);
	if (d < p) quick_sort(d, p, a);
	if (l < g) quick_sort(l, g, a);
}


int main()
{
	float * a = new float[n];
	unsigned long int m;
	int k;
	time_t t;
	srand((unsigned)time(&t));
	clock_t tp, tk;
	double tc;
	cout << "Podaj ilosc wyrazow ciagu ";
	cin >> m;
	//cout << "ciag wylosowany" << "\n";
	for (unsigned long int i = 1; i <= m; i++)
	{

		a[i] = rand() % 10000;
		//cout << a[i] << "\t";
	}
	//cout << "\n";
	do
	{
		cout << "Podaj procedury" << "\n" << "1: Procedura babelkowa" << "\n" << "2: Procedura wstawianie" << "\n" << "3: Procedura scalania" << "\n" << "4: Procedura quick sort" << endl;
		cin >> k;
		switch (k)
		{
		case 1:
		{
				  cout << "Wybrales sortowanie babelkowe ";
				  tp = clock();
				  bubble_sort(m, a);
				  tk = clock();
				  break;
		}
		case 2:{
				   cout << "Wybrales sortowanie wstawianie ";
				   tp = clock();
				   sort_insert(m, a);
				   tk = clock();
				   break;
		}
		case 3:{
				   cout << "Wybrales sortowanie scalanie ";
				   tp = clock();
				   sort_scal(1, m, a);
				   tk = clock();
				   break;
		}
		case 4:{
				   cout << "Wybrales sortowanie quick sort ";
				   tp = clock();
				   quick_sort(1, m, a);
				   tk = clock();
				   break;
		}
			
		case 0:{
				   break;
		}

		}
		//cout << "ciag posortowany" << "\n";

		for (unsigned long int i = 1; i <= m; i++)
			//cout << a[i] << "\t";
		//cout << "\n";

		tc = (tk - tp) / double(CLOCKS_PER_SEC);
		cout << "Czas sortowania = " << tc << "\n";
	} while (k != 0);
	return 0;
}