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

#define MAX 10000

int arr[MAX], n;
int comparisons, swaps;

void displayArray(int a[], int size){
	for(int i = 0; i < size; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void swap(int *a, int *b){
	int temp = *a;
	*a = *b;
	*b = temp;
	swaps++;
}

void copyArray(int src[], int dest[], int size){
	for(int i = 0; i < size; i++)
		dest[i] = src[i];
}

void readArray(){
	printf("Enter number of elements: ");
	scanf("%d", &n);
	printf("Enter %d elements: ", n);
	for(int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
}

void generateRandom(){
	printf("Enter number of elements: ");
	scanf("%d", &n);
	srand(time(NULL));
	for(int i = 0; i < n; i++)
		arr[i] = rand() % 1000;
	printf("Generated %d random elements.\n", n);
}

/* ======================== BUBBLE SORT ======================== */
void bubbleSort(int a[], int size){
	comparisons = 0; swaps = 0;
	for(int i = 0; i < size - 1; i++){
		int swapped = 0;
		for(int j = 0; j < size - i - 1; j++){
			comparisons++;
			if(a[j] > a[j+1]){
				swap(&a[j], &a[j+1]);
				swapped = 1;
			}
		}
		if(!swapped) break;
	}
	printf("Bubble Sort: %d comparisons, %d swaps\n", comparisons, swaps);
}

/* ====================== SELECTION SORT ====================== */
void selectionSort(int a[], int size){
	comparisons = 0; swaps = 0;
	for(int i = 0; i < size - 1; i++){
		int minIdx = i;
		for(int j = i + 1; j < size; j++){
			comparisons++;
			if(a[j] < a[minIdx])
				minIdx = j;
		}
		if(minIdx != i)
			swap(&a[i], &a[minIdx]);
	}
	printf("Selection Sort: %d comparisons, %d swaps\n", comparisons, swaps);
}

/* ====================== INSERTION SORT ====================== */
void insertionSort(int a[], int size){
	comparisons = 0; swaps = 0;
	for(int i = 1; i < size; i++){
		int key = a[i];
		int j = i - 1;
		while(j >= 0){
			comparisons++;
			if(a[j] > key){
				a[j+1] = a[j];
				swaps++;
				j--;
			} else break;
		}
		a[j+1] = key;
	}
	printf("Insertion Sort: %d comparisons, %d swaps\n", comparisons, swaps);
}

/* ======================== MERGE SORT ======================== */
void merge(int a[], int left, int mid, int right){
	int n1 = mid - left + 1;
	int n2 = right - mid;
	int L[MAX], R[MAX];
	for(int i = 0; i < n1; i++) L[i] = a[left + i];
	for(int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];

	int i = 0, j = 0, k = left;
	while(i < n1 && j < n2){
		comparisons++;
		if(L[i] <= R[j])
			a[k++] = L[i++];
		else
			a[k++] = R[j++];
	}
	while(i < n1) a[k++] = L[i++];
	while(j < n2) a[k++] = R[j++];
}

void mergeSort(int a[], int left, int right){
	if(left < right){
		int mid = left + (right - left) / 2;
		mergeSort(a, left, mid);
		mergeSort(a, mid + 1, right);
		merge(a, left, mid, right);
	}
}

/* ======================== QUICK SORT ======================== */
int partition(int a[], int low, int high){
	int pivot = a[high];
	int i = low - 1;
	for(int j = low; j < high; j++){
		comparisons++;
		if(a[j] < pivot){
			i++;
			swap(&a[i], &a[j]);
		}
	}
	swap(&a[i+1], &a[high]);
	return i + 1;
}

void quickSort(int a[], int low, int high){
	if(low < high){
		int pi = partition(a, low, high);
		quickSort(a, low, pi - 1);
		quickSort(a, pi + 1, high);
	}
}

/* ======================== BENCHMARK ======================== */
void benchmark(){
	int sizes[] = {100, 1000, 5000};
	int numSizes = 3;
	int temp[MAX];
	clock_t start, end;

	printf("\n========================================\n");
	printf("       SORTING ALGORITHM BENCHMARK\n");
	printf("========================================\n");
	printf("%-12s %-8s %-12s %-10s %-10s\n", "Algorithm", "Size", "Comparisons", "Swaps", "Time(ms)");
	printf("------------------------------------------------------------\n");

	for(int s = 0; s < numSizes; s++){
		int sz = sizes[s];
		int testArr[MAX];
		srand(42); // fixed seed for reproducibility
		for(int i = 0; i < sz; i++) testArr[i] = rand() % 10000;

		// Bubble Sort
		copyArray(testArr, temp, sz);
		comparisons = 0; swaps = 0;
		start = clock();
		bubbleSort(temp, sz);
		end = clock();
		printf("%-12s %-8d %-12d %-10d %-10.2f\n", "Bubble", sz, comparisons, swaps,
			(double)(end-start)*1000/CLOCKS_PER_SEC);

		// Selection Sort
		copyArray(testArr, temp, sz);
		comparisons = 0; swaps = 0;
		start = clock();
		selectionSort(temp, sz);
		end = clock();
		printf("%-12s %-8d %-12d %-10d %-10.2f\n", "Selection", sz, comparisons, swaps,
			(double)(end-start)*1000/CLOCKS_PER_SEC);

		// Insertion Sort
		copyArray(testArr, temp, sz);
		comparisons = 0; swaps = 0;
		start = clock();
		insertionSort(temp, sz);
		end = clock();
		printf("%-12s %-8d %-12d %-10d %-10.2f\n", "Insertion", sz, comparisons, swaps,
			(double)(end-start)*1000/CLOCKS_PER_SEC);

		// Merge Sort
		copyArray(testArr, temp, sz);
		comparisons = 0; swaps = 0;
		start = clock();
		mergeSort(temp, 0, sz - 1);
		end = clock();
		printf("%-12s %-8d %-12d %-10s %-10.2f\n", "Merge", sz, comparisons, "N/A",
			(double)(end-start)*1000/CLOCKS_PER_SEC);

		// Quick Sort
		copyArray(testArr, temp, sz);
		comparisons = 0; swaps = 0;
		start = clock();
		quickSort(temp, 0, sz - 1);
		end = clock();
		printf("%-12s %-8d %-12d %-10d %-10.2f\n", "Quick", sz, comparisons, swaps,
			(double)(end-start)*1000/CLOCKS_PER_SEC);

		printf("------------------------------------------------------------\n");
	}
}

int main(){
	int choice, temp[MAX];

	printf("\n========================================\n");
	printf("   SORTING ALGORITHMS IMPLEMENTATION\n");
	printf("========================================\n");

	do {
		printf("\n--- Sorting Menu ---\n");
		printf("1. Enter array manually\n");
		printf("2. Generate random array\n");
		printf("3. Bubble Sort\n");
		printf("4. Selection Sort\n");
		printf("5. Insertion Sort\n");
		printf("6. Merge Sort\n");
		printf("7. Quick Sort\n");
		printf("8. Display current array\n");
		printf("9. Run Benchmark (compare all)\n");
		printf("0. Exit\n");
		printf("Enter choice: ");
		scanf("%d", &choice);

		switch(choice){
			case 1:
				readArray();
				break;
			case 2:
				generateRandom();
				break;
			case 3:
				if(n == 0){ printf("Enter array first!\n"); break; }
				copyArray(arr, temp, n);
				printf("Before: "); displayArray(temp, n);
				bubbleSort(temp, n);
				printf("After:  "); displayArray(temp, n);
				break;
			case 4:
				if(n == 0){ printf("Enter array first!\n"); break; }
				copyArray(arr, temp, n);
				printf("Before: "); displayArray(temp, n);
				selectionSort(temp, n);
				printf("After:  "); displayArray(temp, n);
				break;
			case 5:
				if(n == 0){ printf("Enter array first!\n"); break; }
				copyArray(arr, temp, n);
				printf("Before: "); displayArray(temp, n);
				insertionSort(temp, n);
				printf("After:  "); displayArray(temp, n);
				break;
			case 6:
				if(n == 0){ printf("Enter array first!\n"); break; }
				copyArray(arr, temp, n);
				printf("Before: "); displayArray(temp, n);
				comparisons = 0;
				mergeSort(temp, 0, n - 1);
				printf("Merge Sort: %d comparisons\n", comparisons);
				printf("After:  "); displayArray(temp, n);
				break;
			case 7:
				if(n == 0){ printf("Enter array first!\n"); break; }
				copyArray(arr, temp, n);
				printf("Before: "); displayArray(temp, n);
				comparisons = 0; swaps = 0;
				quickSort(temp, 0, n - 1);
				printf("Quick Sort: %d comparisons, %d swaps\n", comparisons, swaps);
				printf("After:  "); displayArray(temp, n);
				break;
			case 8:
				if(n == 0){ printf("No array loaded!\n"); break; }
				printf("Array: "); displayArray(arr, n);
				break;
			case 9:
				benchmark();
				break;
			case 0:
				printf("Exiting...\n");
				break;
			default:
				printf("Invalid choice!\n");
		}
	} while(choice != 0);

	return 0;
}