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

#define N	1000
#define R	0xF

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 n, int exp) {
	static int tmp[N];
	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) {
	int m = getMaxValue(arr, n);

	for (int exp = 0; (m >> exp) > 0; exp += 4)
		countSort(arr, n, exp);
}

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();
		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;
}