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

#define SIZE 1000000

void swap(int *var1, int *var2) {
	int temp = *var1;
	*var1 = *var2;
	*var2 = temp;
}

void choosePivot(int *array, int first, int last) {
	int middle = (first + last) / 2;

	if (array[first] < array[last]) {
		if (array[first] < array[middle] && array[middle] < array[last]) {
			swap(&array[first], &array[middle]);
		}
	}
	else {
		if (array[last] < array[middle] && array[middle] < array[first]) {
			swap(&array[first], &array[middle]);
		}
		else {
			swap(&array[first], &array[last]);
		}
	}
}

void partition(int *array, int first, int last, int *pivot) {
	choosePivot(array, first, last);

	*pivot = array[first];

	int last_sort = first;
	int unknown = first + 1;

	for (; unknown <= last; unknown++) {
		if (array[unknown] < *pivot) {
			last_sort++;
			swap(&array[unknown], &array[last_sort]);
		}
	}

	swap(&array[first], &array[last_sort]);
	*pivot = last_sort;
}

void quickSort(int *array, int first, int last) {
	int pivot_index;
	
	if (first < last) {
		partition(array, first, last, &pivot_index);
		quickSort(array, first, pivot_index - 1);
		quickSort(array, pivot_index + 1, last);
	}
}

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

void filltArray(int *array, int size) {	
	time_t t;
	srand((unsigned)time(&t));

	int i = 0;
	for (; i < size; i++) {
		 array[i] = rand() % 65535;
	}
}

int main() {
	int array[SIZE] = {};
	clock_t t1, t2;

	filltArray(array, sizeof(array) / sizeof(int));
	printf("Before sorting: \n");
	//printArray(array, sizeof(array)/sizeof(int));
	t1 = clock();
	quickSort(array, 0, sizeof(array) / sizeof(int)-1);
	t2 = clock();
	printf("\nAfter sorting: \n");
	//printArray(array, sizeof(array) / sizeof(int));

	float diff = ((float)(t2 - t1) / 1000000.0F ) * 1000;   
    printf("Time taken = %f",diff); 

	// #include <sys/time.h>

	// struct timeval stop, start;
	// gettimeofday(&start, NULL);
	// //do stuff
	// gettimeofday(&stop, NULL);
	// printf("took %lu\n", stop.tv_usec - start.tv_usec);

	return 0;
}

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

#define SIZE 100

void merge(int *array, int left, int right, int mid) {
	int tempArray[SIZE] = {};
	int pos = left;
	int lpos = left;
	int rpos = mid + 1;

	while (lpos <= mid && rpos <= right) {
		if (array[lpos] < array[rpos]) {
			tempArray[pos++] = array[lpos++];
		}
		else {
			tempArray[pos++] = array[rpos++];
		}
	}

	while (lpos <= mid) {
		tempArray[pos++] = array[lpos++];
	}
	while (rpos <= right) {
		tempArray[pos++] = array[rpos++];
	}

	int i = left;
	while (i <= right) {
		array[i] = tempArray[i++];
	}
}

void mergeSort(int *array, int left, int right) {
	if (left < right) {
		int mid = (left + right)/2;

		mergeSort(array, left, mid);
		mergeSort(array, mid + 1, right);

		merge(array, left, right, mid);
	}
}

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

void filltArray(int *array, int size) {
	time_t t;
	srand((unsigned)time(&t));

	int i = 0;
	for (; i < size; i++) {
		array[i] = rand() % 100;
	}
}

int main() {
	int array[SIZE] = {};

	filltArray(array, sizeof(array)/sizeof(int));
	printf("Before sorting: \n");
	printArray(array, sizeof(array)/sizeof(int));

	mergeSort(array, 0, sizeof(array)/sizeof(int) - 1);
	printf("\nAfter sorting: \n");
	printArray(array, sizeof(array)/sizeof(int));
	getchar();

	return 0;
}
<file_sep>#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 10

typedef struct {
	int last;
	int size;
	int *array;
} Heap;

void swap(int *, int *);
void printArray(int *, int);
void filltArray(int *, int);

Heap *heapCreate() {
	Heap *heap = (Heap *)malloc(sizeof(Heap));

	heap->last = 0;
	heap->size = SIZE;
	heap->array = (int *)malloc(sizeof(int) * heap->size);

	return heap;
}

void heapDestroy(Heap *heap) {
	free(heap->array);
	heap = NULL;
}

void heapShiftUp(Heap *heap) {
	int child = heap->last - 1;
	int parent = (heap->last - 2) / 2;

	while (heap->array[child] > heap->array[parent]) {
		swap(&heap->array[child], &heap->array[parent]);
		child = parent;
		parent = (parent - 1) / 2;
	}
}

int heapInsert(Heap *heap, int data) {
	if (heap->last >= heap->size) {
		printf("Heap is full\n");
		return -1;
	}

	heap->array[heap->last++] = data;

	if (heap->last >= 2) {
		heapShiftUp(heap);
	}

	return 0;
}

Heap *heapify(int *array, int size) {
	Heap *heap = heapCreate();

	if (size > heap->size) {
		printf("Array is larger than maximum heap size\n");
		return NULL;
	}	

	int i = 0;
	for (; i < size; i++) {
		heapInsert(heap, array[i]);
	}

	return heap;
}

void heapShiftDown(Heap *heap) {
	int parent = 0;
	int child = 2 * parent + 1;

	while (heap->array[child] > heap->array[parent] && 2 * child + 1 < heap->size) {
		swap(&heap->array[child], &heap->array[parent]);
		parent = child;
		child = 2 * child + 1;
	}
}

int heapRemove(Heap *heap, int *data) {
	if (heap->array <= 0) {
		printf("Heap is empty\n");
		return -1;
	}

	swap(&heap->array[0], &heap->array[heap->last - 1]);
	*data = heap->array[heap->last - 1];
	heap->array[heap->last - 1] = NULL;
	heap->last--;
	heapShiftDown(heap);

	return 0;
}

void heapSort(int *array, int size) {
    Heap *heap = heapify(array, size);

    while (heap->last > 1) {
		printf("Before: ");
		printArray(heap->array, SIZE);
		swap(&heap->array[heap->last - 1], &heap->array[0]);
		heap->last--;
		heapShiftDown(heap);
		printf("After: ");
		printArray(heap->array, SIZE);
    }

	*array = *heap->array;
}

int main() {
	int array[SIZE] = { 8, 10, 15, 3, 30, 55, 2, 9, 41, 16 };

	/*filltArray(array, sizeof(array)/sizeof(int));

	printf("Before heapify: \n");
	printArray(array, sizeof(array) / sizeof(int));

	Heap* heap = heapify(array, sizeof(array) / sizeof(int));
	printf("\nAfter heapify: \n");
	printArray(heap->array, sizeof(array) / sizeof(int));*/

	printf("Before sort: \n");
	printArray(array, sizeof(array) / sizeof(int));

	heapSort(array, sizeof(array) / sizeof(int));
	printf("\nAfter sort: \n");
	printArray(array, sizeof(array) / sizeof(int));
	getchar();

	return 0;
}

void swap(int *var1, int *var2) {
	int temp = *var1;
	*var1 = *var2;
	*var2 = temp;
}

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

void filltArray(int *array, int size) {
	time_t t;
	srand((unsigned)time(&t));

	int i = 0;
	for (; i < size; i++) {
		array[i] = rand() % 100;
	}
}

<file_sep># sort
heap, merge and quick sort in C
