#include <windows.h>
#include <stdio.h>
#include <math.h>
#include <time.h>

#define ARRAYSIZE (1024 * 64)
// 64K elements in benchmark arrays

int compare(const int *a, const int *b)
// Comparison function to be used with the CRT qsort
{
	return *a - *b;
}

void my_qsort(int *left, int *right)
// by Matt Whitlock, May 2003
{
	int *leftbound, *rightbound, pivot, temp;

	pivot = left[((UINT_PTR)right - (UINT_PTR)left) / (2 * sizeof(int))];
	leftbound = left;
	rightbound = right;
	for (;;) {
		while (*leftbound < pivot) {
			leftbound++;
		}
		while (*rightbound > pivot) {
			rightbound--;
		}
		while ((leftbound != rightbound) && (*leftbound == *rightbound)) {
			leftbound++;
		}
		if (leftbound == rightbound) {
			break;
		}
		temp = *leftbound;
		*leftbound = *rightbound;
		*rightbound = temp;
	}
	if (left < --leftbound) {
		my_qsort(left, leftbound);
	}
	if (right > ++rightbound) {
		my_qsort(rightbound, right);
	}
}

void their_qsort(int *left, int *right)
// Adapted from a macro definition posted on SourceForge by evildave
{
	int *pivot;

	{
		int *pRight = right;
		int *pLeft = left;
		int scratch = *left;

		while (pLeft < pRight) {
			while ((*pRight > scratch) && (pLeft < pRight)) {
				pRight--;
			}
			if (pLeft != pRight) {
				*pLeft = *pRight;
				pLeft++;
			}
			while ((*pLeft < scratch) && (pLeft < pRight)) {
				pLeft++;
			}
			if (pLeft != pRight) {
				*pRight = *pLeft;
				pRight--;
			}
		}
		*pLeft = scratch;
		pivot = pLeft;
	}
	if (left < pivot) {
		their_qsort(left, pivot - 1);
	}
	if (right > pivot) {
		their_qsort(pivot + 1, right);
	}
}

int main()
{
	int *arr1, *arr2, *arr3, i;
	LARGE_INTEGER li1, li2;

	arr1 = new int[ARRAYSIZE];
	arr2 = new int[ARRAYSIZE];
	arr3 = new int[ARRAYSIZE];


	puts("Populating array 1 with random integers...");
	srand(time(0));
	for (i = 0; i < ARRAYSIZE; i++) {
		arr1[i] = rand();
	}
	puts("Duplicating array 1 to array 2...");
	memcpy(arr2, arr1, ARRAYSIZE * sizeof(int));
	puts("Duplicating array 1 to array 3...");
	memcpy(arr3, arr1, ARRAYSIZE * sizeof(int));

	puts("\nSorting array 1 with qsort...");
	QueryPerformanceCounter(&li1);
	qsort(arr1, ARRAYSIZE, sizeof(int), (int (__cdecl *)(const void *, const void *))compare);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));

	puts("\nSorting array 2 with my_qsort...");
	QueryPerformanceCounter(&li1);
	my_qsort(arr2, arr2 + ARRAYSIZE - 1);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));

	puts("\nSorting array 3 with their_qsort...");
	QueryPerformanceCounter(&li1);
	their_qsort(arr3, arr3 + ARRAYSIZE - 1);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));


	puts("\n\nPopulating array 1 with sequential ascending integers...");
	for (i = 0; i < ARRAYSIZE; i++) {
		arr1[i] = i;
	}
	puts("Duplicating array 1 to array 2...");
	memcpy(arr2, arr1, ARRAYSIZE * sizeof(int));
	puts("Duplicating array 1 to array 3...");
	memcpy(arr3, arr1, ARRAYSIZE * sizeof(int));

	puts("\nSorting array 1 with qsort...");
	QueryPerformanceCounter(&li1);
	qsort(arr1, ARRAYSIZE, sizeof(int), (int (__cdecl *)(const void *, const void *))compare);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));

	puts("\nSorting array 2 with my_qsort...");
	QueryPerformanceCounter(&li1);
	my_qsort(arr2, arr2 + ARRAYSIZE - 1);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));

	puts("\nSorting array 3 with their_qsort...");
	QueryPerformanceCounter(&li1);
	their_qsort(arr3, arr3 + ARRAYSIZE - 1);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));


	puts("\n\nPopulating array 1 with sequential descending integers...");
	for (i = 0; i < ARRAYSIZE; i++) {
		arr1[i] = ARRAYSIZE - i;
	}
	puts("Duplicating array 1 to array 2...");
	memcpy(arr2, arr1, ARRAYSIZE * sizeof(int));
	puts("Duplicating array 1 to array 3...");
	memcpy(arr3, arr1, ARRAYSIZE * sizeof(int));

	puts("\nSorting array 1 with qsort...");
	QueryPerformanceCounter(&li1);
	qsort(arr1, ARRAYSIZE, sizeof(int), (int (__cdecl *)(const void *, const void *))compare);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));

	puts("\nSorting array 2 with my_qsort...");
	QueryPerformanceCounter(&li1);
	my_qsort(arr2, arr2 + ARRAYSIZE - 1);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));

	puts("\nSorting array 3 with their_qsort...");
	QueryPerformanceCounter(&li1);
	their_qsort(arr3, arr3 + ARRAYSIZE - 1);
	QueryPerformanceCounter(&li2);
	printf("Time: %d\n", (int)(li2.QuadPart - li1.QuadPart));


	delete[] arr3;
	delete[] arr2;
	delete[] arr1;

	return 0;
}