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

void Swap(int* a, int* b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

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 arr[], int low, int high)
{
	if (low < high)
	{
		int pi = partition(arr, low, high);

		QuickSort(arr, low, pi - 1);
		QuickSort(arr, pi + 1, high);
	}
}

int Min(int arr[], int from, int size) {
	int minEl = arr[from];
	int minPos = from;
	for (int i = from; i < size; i++) {
		if (arr[i] < minEl) {
			minEl = arr[i];
			minPos = i;
		}
	}
	return minPos;
}

void SelectionSort(int arr[], int size) {
	for (int i = 0; i < size - 1; i++) {
		Swap(&arr[i], &arr[Min(arr, i, size)]);
	}
}

#define SIZE 10000

int main(void) {
	srand((unsigned int)time(NULL));
	int arr1[SIZE];
	int arr2[SIZE];
	for (int i = 0; i < SIZE; i++) {
		arr1[i] = rand() % 100;
		arr2[i] = arr1[i];
	}

	clock_t start, end;
	start = clock();
	QuickSort(arr1, 0, SIZE - 1);
	end = clock();
	printf("Quick sort took %lf\n", ((double)end - (double)start) / 1000);

	start = clock();
	SelectionSort(arr2, SIZE);
	end = clock();
	printf("Selection sort took %lf\n", ((double)end - (double)start) / 1000);

	int sortedSame = 1;
	for (int i = 0; i < 10; i++) {
		if (arr1[i] != arr2[i]) {
			sortedSame = 0;
			printf("Error.\n");
			break;
		}
	}
	if (sortedSame) {
		printf("Arrays sorted equally.\n");
	}


	return;
}