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