fork download 
  1. #include <iostream>
  2. #include <random>
  3. #include <chrono>
  4. #include <ctime>
  5. #include <cstdlib>
  6.  
  7. #define N	10000
  8. #define R	0xF
  9. #define R_4	4
  10.  
  11. using namespace std;
  12.  
  13. int getMaxValue(int arr[], int n) {
  14. 	int max = arr[0];
  15.  
  16. 	for (int i = 1; i < N; i++) {
  17. 		if (arr[i] > max)
  18. 			max = arr[i];
  19. 	}
  20. 	return max;
  21. }
  22.  
  23. void countSort(int arr[], int n, int exp) {
  24. 	int tmp[N];
  25. 	int numberCnt[R] = { 0 };
  26. 	int i;
  27.  
  28. 	for (i = 0; i < n; i++)
  29. 		numberCnt[(arr[i] >> exp) & 0xF]++;
  30.  
  31. 	for (i = 1; i < R; i++)
  32. 		numberCnt[i] += numberCnt[i - 1];
  33.  
  34. 	for (i = n - 1; i >= 0; i--) {
  35. 		tmp[numberCnt[(arr[i] >> exp) & 0xF] - 1] = arr[i];
  36. 		numberCnt[(arr[i] >> exp) & 0xF]--;
  37. 	}
  38.  
  39. 	for (i = 0; i < n; i++)
  40. 		arr[i] = tmp[i];
  41. }
  42.  
  43. void radixSort(int arr[], int n) {
  44. 	int m = getMaxValue(arr, n);
  45.  
  46. 	for (int exp = 0; (m >> exp) > 0; exp += 4)
  47. 		countSort(arr, n, exp);
  48. }
  49.  
  50. void print(int arr[], int n) {
  51. 	for (int i = 0; i < n; i++) {
  52. 		cout << arr[i] << " ";
  53. 	}
  54. 	cout << endl;
  55. }
  56.  
  57. int compare(const void *first, const void *second) {
  58. 	if (*(int*)first > *(int*)second)
  59. 		return 1;
  60. 	else if (*(int*)first < *(int*)second)
  61. 		return -1;
  62. 	else
  63. 		return 0;
  64. }
  65.  
  66. int main(void) {
  67.  
  68. 	//int arr[N] = { 89,70,35,131,910 };
  69. 	int arr[N];
  70. 	int arr2[N];
  71.  
  72. 	chrono::system_clock::time_point StartTime, EndTime;
  73. 	chrono::microseconds micro;
  74.  
  75. 	mt19937 rnd((unsigned)time(NULL));
  76. 	uniform_int_distribution<int> dist(0, 9999);
  77.  
  78. 	for (int k = 0; k < 20; k++) {
  79. 		for (int i = 0; i < N; i++)
  80. 			arr[i] = dist(rnd);
  81.  
  82. 		memcpy(arr2, arr, sizeof(int)*N);
  83.  
  84. 		int n = sizeof(arr) / sizeof(int);
  85.  
  86. 		StartTime = chrono::system_clock::now();
  87. 		radixSort(arr, n);
  88. 		EndTime = chrono::system_clock::now();
  89. 		micro = chrono::duration_cast<chrono::microseconds>(EndTime - StartTime);
  90. 		cout << "Radix Sort : " << micro.count() << "μs, ";
  91.  
  92. 		StartTime = chrono::system_clock::now();
  93. 		qsort(arr2, N, sizeof(int), compare);
  94. 		EndTime = chrono::system_clock::now();
  95. 		micro = chrono::duration_cast<chrono::microseconds>(EndTime - StartTime);
  96. 		cout << "qsort Function : " << micro.count() << "μs" << endl;
  97.  
  98. 		//print(arr, n);
  99. 		//print(arr2, n);
  100. 	}
  101.  
  102. 	return 0;
  103. }
  104.  
  105.  
  106.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:82:34: error: 'memcpy' was not declared in this scope
   memcpy(arr2, arr, sizeof(int)*N);
                                  ^
stdout 
Standard output is empty
https://ideone.com/3lEK5a
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!