#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
typedef enum { false, true } bool;
void citire(int v[], int* n)
{

	srand(time(NULL));
	*n = rand() % 20;
	printf("Vectorul va avea %d elemente\n", *n);
	for (int i = 0; i < *n; i++)
	{
		v[i] = rand() % 50;
	}

}
void afisare(int v[], int N)
{
	int i;
	for (i = 0; i < N; i++)
	{
		printf("%d ", v[i]);
	}
	printf("\n");
}
void afisare1(int v[], int N)
{
	int i;
	for (i = 1; i <= N; i++)
	{
		printf("%d ", v[i]);
	}
	printf("\n");
}
void shellsort(int v[], int N)
{
	int h[] = { 3, 2, 1 };
	int i, j, k, w, aux;
	for (w = 0; w < 3; w++)
	{
		k = h[w];
		for (i = k; i < N; i=i+k)
		{
			int aux = v[i];
			int j = i - k;
			while (j >= 0 && v[j] > aux)
			{
				v[j + k] = v[j];
				j=j-k;
			}
			v[j + k] = aux;
		}
	}
}


void deplasare(int v[], int s, int d,int N)
{
	int i, j, x;
	int b = 0;

	i = s;
	j = 2 * i;
	x = v[i];

	while ((j <= d) && (b == 0))
	{
		if (j < d)
		{
			if (v[j] < v[j + 1])
				j++;
		}

		if (x < v[j])
		{
			v[i] = v[j];
			i = j;
			j = 2 * i;
		}
		else
		{
			b = 1;
		}
		afisare1(v,N );
	}
	v[i] = x;
}
void heapsort(int v[], int n)
{
	int s, d, aux;
	
	s = n / 2 + 1;
	d = n;

	while (s > 1)
	{
		s--;
		deplasare(v, s, n,n);
	}

	while (d > 1)
	{
		aux = v[1];
		v[1] = v[d];
		v[d] = aux;
		d--;
		deplasare(v, 1, d,n);
	}
}
void quicksort(int a[], int s, int d)
{
	int i=s, j=d, x;
	int aux;

	x = a[(s + d) / 2];
	do
	{
		while (a[i] <= x && i< d)
		{
			i++;
		}
		while (a[j] > x && j>s)
		{
			j--;
		}
		if (i <= j)
		{
		   aux = a[i];
			a[i] = a[j];
			a[j] = aux;
			i++;
			j--;
		}

	} while (i <= j);
	if (j > s)
	{
		quicksort(a, s, j);
	}
	if (i < d)
	{
		quicksort(a, i, d);
	}

}
void mutare(int a[], int b[], int N)
{
	for (int i = 0; i < N; i++)
	{
		b[i + 1] = a[i];
	}
}
int main()
{
	int v[100], v1[100], N, opt;
	
	citire(v, &N);
	afisare(v, N);
	do {
		printf("0. Iesire\n1. ShellSort\n2. Heapsort\n3. Selectie\n4. Selectie Performanta\n5. Interschimbare\n6. Shakesort\n");
		printf("Alegeti optiune: ");
		scanf("%d", &opt);
		switch (opt)
		{
		case 1:
			shellsort(v, N);
			printf("Vectorul sortat prin ShellSort este: \n");
			afisare(v, N);
			break;
		case 2:
			mutare(v, v1, N);
			heapsort(v1, N);
			printf("Vectorul sortat prin Heapsort este: \n");
			afisare1(v1,N);
			break;
		case 3:
			mutare(v, v1, N);
			quicksort(v1,1,N);
			printf("Vectorul sortat prin Quicksort este: \n");
			afisare1(v1, N);
			break;
		
		}
	} while (opt);

	return 0;

}