#include <iostream>
#include <random>
#include <chrono>
#include <ctime>
#include <cstdlib>
#include <algorithm>

#define N	10000
#define R	16

using namespace std;

int getMaxValue(int arr[], int n) {
	int max = 0;
	for (int i = 0; i < N; i++) {
		max |= arr[i];
	}
	return max;
}

void countSort(int* arr, int *tmp, int n, int exp ) {
	int numberCnt[R] = { 0 };
	int i;

	for (i = 0; i < n; i++)
		numberCnt[(arr[i] >> exp) & 0xF]++;

	for (i = 1; i < R; i++)
		numberCnt[i] += numberCnt[i - 1];

	for (i = n - 1; i >= 0; i--) {
		tmp[numberCnt[(arr[i] >> exp) & 0xF] - 1] = arr[i];
		numberCnt[(arr[i] >> exp) & 0xF]--;
	}

	//for (i = 0; i < n; i++)
	//	arr[i] = tmp[i];
}

void radixSort(int arr[], int n) {
	static int *tmp = new int[N];

	int m = getMaxValue(arr, n);
	int* pages[] = { arr, tmp };	
	int page_index = 0;
	
	for (int exp = 0; (m >> exp) > 0; exp += 4, page_index^=1)
		countSort(pages[page_index], pages[page_index ^ 1], n, exp);

	delete[]tmp;
}

void print(int arr[], int n) {
	for (int i = 0; i < n; i++) 
		cout << arr[i] << " ";
	
	cout << endl;
}

int compare(const void *first, const void *second) {
	if (*(int*)first > *(int*)second)
		return 1;
	else if (*(int*)first < *(int*)second)
		return -1;
	else
		return 0;
}

int main(void) {

	//int arr[N] = { 89,70,35,131,910 };
	int arr[N];
	int arr2[N];

	chrono::system_clock::time_point StartTime, EndTime;
	chrono::microseconds micro;

	mt19937 rnd((unsigned)time(NULL));
	uniform_int_distribution<int> dist(0, 9999);

	for (int k = 0; k < 1; k++) {
		for (int i = 0; i < N; i++)
			arr[i] = dist(rnd);

		memcpy(arr2, arr, sizeof(int)*N);

		int n = sizeof(arr) / sizeof(int);

		StartTime = chrono::system_clock::now();
		radixSort(arr, n);
		EndTime = chrono::system_clock::now();
		micro = chrono::duration_cast<chrono::microseconds>(EndTime - StartTime);
		cout << "Radix Sort : " << micro.count() << "μs, ";

		StartTime = chrono::system_clock::now();
		//sort(&arr2[0], &arr2[N - 1]);
		qsort(arr2, N, sizeof(int), compare);
		EndTime = chrono::system_clock::now();
		micro = chrono::duration_cast<chrono::microseconds>(EndTime - StartTime);
		cout << "qsort Function : " << micro.count() << "μs" << endl;

		print(arr, n);
		//print(arr2, n);
	}

	return 0;
}