#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>

int N, count = 1;
int pasi;
void swap(int* a, int* b)
{
	int t = *a;
	*a = *b;
	*b = t;
}
void citire(int a[], int n)
{
	int i;
	printf("Dati cele %d numere: ", n);
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
}
void afisare(int a[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}
void interschimbare(int a[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++) {
		for (j = i + 1; j < n; j++) {
			if (a[i] > a[j]) {
				int aux = a[i];
				a[i] = a[j];
				a[j] = aux;
			}
		}
		printf("Etapa %d: ", count);
		count++;
		afisare(a, n);
	}
}

void insertie(int a[], int n)
{
	int i, j, aux;
	for (i = 1; i < n; i++)
	{
		aux = a[i];
		j = i - 1;
		while (j >= 0 && a[j] > aux)
		{
			a[j + 1] = a[j];
			j = j - 1;
		}

		a[j + 1] = aux;
		printf("Etapa %d: ", i);
		afisare(a, n);
	}
}

int cautareBinara(int a[], int cautat, int s, int d)
{
	if (d <= s)
	{
		if (cautat > a[s])
			return (s + 1);
		else
			return s;
	}
	int m = (s + d) / 2;
	if (cautat == a[m])
		return m + 1;
	if (cautat > a[m])
		return cautareBinara(a, cautat, m + 1, d);
	return cautareBinara(a, cautat, s, m - 1);
}

void insertieBinara(int a[], int n)
{
	int i, j, aux, loc;
	for (i = 1; i < n; i++)
	{
		j = i - 1;
		aux = a[i];
		loc = cautareBinara(a, aux, 0, j);
		while (j >= loc)
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = aux;
		printf("\nEtapa %d: ", i);
		afisare(a, n);
	}
}

void selectie(int a[], int n)
{
	int i, j, k_min, aux;
	for (i = 0; i < n - 1; i++)
	{
		k_min = i;
		aux = a[i];
		for (j = i + 1; j < n; j++)
			if (a[j] < a[k_min])
			{
				k_min = j;
				aux = a[k_min];
			}
		a[k_min] = a[i];
		a[i] = aux;
		printf("\nEtapa %d: ", i + 1);
		afisare(a, n);
	}
}
void selectiePerformanta(int a[], int n)
{
	int i, j, k_min, aux;
	for (i = 0; i < n - 1; i++)
	{
		k_min = i;
		for (j = i + 1; j < n; j++)
			if (a[j] < a[k_min])
				k_min = j;
		aux = a[k_min];
		a[k_min] = a[i];
		a[i] = aux;
		printf("\nEtapa %d: ", i + 1);
		afisare(a, n);
	}
}

void bubbleSort(int a[], int n)
{
	int i, j, aux;
	for (i = 1; i < n; i++)
	{
		for (j = n - 1; j >= i; j--)
			if (a[j - 1] > a[j])
			{
				aux = a[j - 1];
				a[j - 1] = a[j];
				a[j] = aux;
			}
		printf("\nEtapa %d: ", i);
		afisare(a, n);
	}

}

void shakeSort(int a[], int n)
{
	int  j, k, s, d, aux, count = 1;
	s = 1;
	d = n - 1;
	k = n - 1;
	do
	{
		for (j = d; j >= s; j--)
			if (a[j - 1] > a[j])
			{
				aux = a[j - 1];
				a[j - 1] = a[j];
				a[j] = aux;
				k = j;
			}
		s = k + 1;
		for (j = s; j <= d; j++)
			if (a[j - 1] > a[j])
			{
				aux = a[j - 1];
				a[j - 1] = a[j];
				a[j] = aux;
				k = j;
			}
		d = k - 1;
		printf("\nEtapa %d: ", count);
		afisare(a, n);
		count++;

	} while (s <= d&&count<=pasi);
}
void binsort(int a[], int n)
{
	int i, aux;
	for (i = 0; i < n; i++)
	{
		while (a[i] != i)
		{
			aux = a[a[i]];
			a[a[i]] = a[i];
			a[i] = aux;
		}
		printf("Etapa %d: ", i + 1);
		afisare(a, n);
	}
}

void shellsort(int a[], int n)
{
	int i, j, aux, l, k;
	int h[3] = { 5,3,1 };
	for (l = 0; l < 3; l++)
	{
		k = h[l];
		for (i = k; i < n; i++)
		{
			aux = a[i];
			j = i - k;
			while (j >= 0 && aux < a[j])
			{
				a[j + k] = a[j];
				j = j - k;
			}
			a[j + k] = aux;
		}
		printf("Trecerea %d: ", l + 1);
		afisare(a, n);
	}
}

void heapify(int arr[], int n, int i)
{
	int aux;
	int largest = i; // Initialize largest as root 
	int l = 2 * i + 1; // left = 2*i + 1 
	int r = 2 * i + 2; // right = 2*i + 2 

	// If left child is larger than root 
	if (l < n && arr[l] > arr[largest])
		largest = l;

	// If right child is larger than largest so far 
	if (r < n && arr[r] > arr[largest])
		largest = r;
	// If largest is not root 
	if (largest != i)
	{
		aux = arr[i];
		arr[i] = arr[largest];
		arr[largest] = aux;

		// Recursively heapify the affected sub-tree 
		heapify(arr, n, largest);
	}
}

// main function to do heap sort 
void heapSort(int arr[], int n)
{
	int aux;
	// Build heap (rearrange array) 
	for (int i = n / 2 - 1; i >= 0; i--)
	{
		heapify(arr, n, i);
		printf("Etapa %da: ", n / 2 - i);
		afisare(arr, n);
	}

	// One by one extract an element from heap 
	for (int i = n - 1; i > 0; i--)
	{
		// Move current root to end 
		aux = arr[0];
		arr[0] = arr[i];
		arr[i] = aux;
		printf("Etapa %db: ", n - i);
		afisare(arr, n);
		// call max heapify on the reduced heap 
		heapify(arr, i, 0);
	}
}
int partition(int arr[], int low, int high)
{
	int pivot = arr[high];    // pivot 
	int i = (low - 1);  // Index of smaller element 

	for (int j = low; j <= high - 1; j++)
	{
		// If current element is smaller than the pivot 
		if (arr[j] < pivot)
		{
			i++;    // increment index of smaller element 
			swap(&arr[i], &arr[j]);
		}
	}
	swap(&arr[i + 1], &arr[high]);
	return (i + 1);
}

void quickSort(int a[], int s, int d)
{
	if (s < d)
	{
		int pi = partition(a, s, d);
		printf("Etapa %d: ", count);
		count++;
		afisare(a, N);
		quickSort(a, s, pi - 1);
		quickSort(a, pi, d);
	}
}
int biti(int x, int k, int j)
{
	return (x >> k) & ~(~0 << j);
}
void radix_interschimbare(int a[], int s, int d, int b)
{
	int i, j, aux;
	if (d > s && b >= 0)
	{
		i = s;
		j = d;
		do
		{
			while (i < j && biti(a[i], b, 1) == 0)
				i++;
			while (i < j && biti(a[j], b, 1) == 1)
				j--;
			aux = a[i];
			a[i] = a[j];
			a[j] = aux;

		} while (i != j);
		printf("Etapa %d: ", count);
		count++;
		afisare(a, N);
		if (biti(a[d], b, 1) == 0)
			j++;
		radix_interschimbare(a, s, j - 1, b - 1);
		radix_interschimbare(a, j, d, b - 1);
	}
}
void radix_direct(int a[], int n)
{
	int b, T[100], Numar[100], m, k, i, t;
	b = sizeof(int) * 8;
	m = 4;
	for (t = 0; t < b / m; t++)
	{
		for (i = 0; i < pow(2, m); i++)
			Numar[i] = 0;
		for (i = 0; i < n; i++)
		{
			k = biti(a[i], t * m, m);
			Numar[k]++;
		}
		for (i = 1; i < pow(2, m); i++)
			Numar[i] = Numar[i] + Numar[i - 1];
		for (i = n - 1; i >= 0; i--)
		{
			k = biti(a[i], t * m, m);
			T[Numar[k] - 1] = a[i];
			Numar[k]--;

		}
		printf("Etapa %d: ", t + 1);
		afisare(T, n);
		for (i = 0; i < n; i++)
			a[i] = T[i];
	}
}

int cautare_liniara(int* a, int N)
{
	int x;
	printf("El: ");
	scanf("%d", &x);
	int i;
	for (i = 0; i < N; i++)
	{
		if (a[i] == x)
			return i;
	}
	return -1;
}

int cautare_fanion(int* a, int N)
{
	int x;
	printf("El: ");
	scanf("%d", &x);
	int i = 0;
	a[N] = x;
	while (a[i] != x)
	{
		i++;
	}
	return i;
}

int cautare_binara(int s, int d, int* a)
{
	int x;
	printf("El: ");
	scanf("%d", &x);
	int m;
	if (s > d)
		return -1;
	else
	{
		m = (s + d) / 2;
		if (x == a[m])
			return m;
		if (x < a[m])
			return cautare_binara(s, m - 1, x, a);
		else
			return cautare_binara(m + 1, d, x, a);
	}
}

int cautare_interpolare(int* a, int ic, int sf)
{
	int x;
	printf("El: ");
	scanf("%d", &x);
	if (ic <= sf)
	{
		int m;
		m = ic + (x - a[ic]) * (sf - ic) / (a[sf] - a[ic]);
		if (x == a[m])
			return m + 1;
		else
			if (x < a[m])
				return cautare_interpolare(a, x, ic, m - 1);
			else
				return cautare_interpolare(a, x, m + 1, sf);
	}
	else return 0;
}


int main()
{
	int a[20], n, opt, b,x;
	do
	{
		printf("1.Sortare prin insertie\n");
		printf("2.Sortare prin selectie\n");
		printf("3.Sortare Bubblesort\n");
		printf("4.Shakesort\n");
		printf("5.Binsort\n");
		printf("6.Shellsort\n");
		printf("7.Heap sort(ansamblu invers)\n");
		printf("8.Quicksort\n");
		printf("9.Radix interschimbare\n");
		printf("10.Radix direct\n");
		printf("11.Interschimbare\n");
		printf("12.Cautare liniara\n");
		printf("13.Cautare fanion\n");
		printf("14.Cautare binara\n");
		printf("15.Cautare interpolare\n");
		printf("0.Iesire\n");
		printf("Dati optiunea: ");
		scanf("%d", &opt);
		switch (opt)
		{
		case 1:
			printf("SORTAREA PRIN INSERTIE\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			insertie(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 2:
			printf("\nSORTAREA PRIN SELECTIE\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			selectie(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 3:
			printf("\nBUBLE SORT\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			bubbleSort(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 4:
			printf("\nSHAKE SORT\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			shakeSort(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 5:
			printf("\nBinsort\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			binsort(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 6:
			printf("Shellsort");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			shellsort(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 7:
			printf("\nHEAPSORT\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			heapSort(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 8:
			printf("\nQUICKSORT\n");
			printf("n=");
			scanf("%d", &n);
			N = n;
			count = 1;
			citire(a, n);
			quickSort(a, 0, n - 1);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 9:
			printf("\nRADIX INTERSCHIMBARE\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			b = sizeof(int) * 8;
			N = n;
			count = 1;
			radix_interschimbare(a, 0, n - 1, b - 1);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 10:
			printf("\nRADIX DIRECT\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			radix_direct(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 11:
			printf("\nInterschimbare\n");
			printf("n=");
			scanf("%d", &n);
			citire(a, n);
			interschimbare(a, n);
			printf("\nTabloul dupa sortare:\n");
			afisare(a, n);
			break;
		case 12:
			printf("El: ");
			scanf("%d", &x);
			printf("%d", cautare_liniara(a,n));
			break;
		case 13:
			printf("El: ");
			scanf("%d", &x);
			printf("%d", cautare_fanion(a, n));
			break;
		case 14:
			printf("El: ");
			scanf("%d", &x);
			printf("%d", cautare_binara(0, n - 1, a));
			break;
		case 15:
			printf("El: ");
			scanf("%d", &x);
			printf("%d", cautare_interpolare(a, 0, n - 1));
			break;
		case 0:
			printf("\nAti oprit consola interactiva\n");
			break;
		default:
			printf("\nOPTIUNE INVALIDA\n");
			break;
		}
	} while (opt != 0);
	getch();
	return 0;
}