fork download
copy 
  1. #include <iostream>
  2. #include <random>
  3. #include <chrono>
  4. #include <ctime>
  5. #include <cstdlib>
  6. #include <algorithm>
  7.  
  8. #define N	10000
  9. #define R	16
  10.  
  11. using namespace std;
  12.  
  13. int getMaxValue(int arr[], int n) {
  14. 	int max = 0;
  15. 	for (int i = 0; i < N; i++) {
  16. 		max |= arr[i];
  17. 	}
  18. 	return max;
  19. }
  20.  
  21. void countSort(int* arr, int *tmp, int n, int exp ) {
  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. 	static int *tmp = new int[N];
  42.  
  43. 	int m = getMaxValue(arr, n);
  44. 	int* pages[] = { arr, tmp };	
  45. 	int page_index = 0;
  46.  
  47. 	for (int exp = 0; (m >> exp) > 0; exp += 4, page_index^=1)
  48. 		countSort(pages[page_index], pages[page_index ^ 1], n, exp);
  49.  
  50. 	delete[]tmp;
  51. }
  52.  
  53. void print(int arr[], int n) {
  54. 	for (int i = 0; i < n; i++) 
  55. 		cout << arr[i] << " ";
  56.  
  57. 	cout << endl;
  58. }
  59.  
  60. int compare(const void *first, const void *second) {
  61. 	if (*(int*)first > *(int*)second)
  62. 		return 1;
  63. 	else if (*(int*)first < *(int*)second)
  64. 		return -1;
  65. 	else
  66. 		return 0;
  67. }
  68.  
  69. int main(void) {
  70.  
  71. 	//int arr[N] = { 89,70,35,131,910 };
  72. 	int arr[N];
  73. 	int arr2[N];
  74.  
  75. 	chrono::system_clock::time_point StartTime, EndTime;
  76. 	chrono::microseconds micro;
  77.  
  78. 	mt19937 rnd((unsigned)time(NULL));
  79. 	uniform_int_distribution<int> dist(0, 9999);
  80.  
  81. 	for (int k = 0; k < 1; k++) {
  82. 		for (int i = 0; i < N; i++)
  83. 			arr[i] = dist(rnd);
  84.  
  85. 		memcpy(arr2, arr, sizeof(int)*N);
  86.  
  87. 		int n = sizeof(arr) / sizeof(int);
  88.  
  89. 		StartTime = chrono::system_clock::now();
  90. 		radixSort(arr, n);
  91. 		EndTime = chrono::system_clock::now();
  92. 		micro = chrono::duration_cast<chrono::microseconds>(EndTime - StartTime);
  93. 		cout << "Radix Sort : " << micro.count() << "μs, ";
  94.  
  95. 		StartTime = chrono::system_clock::now();
  96. 		//sort(&arr2[0], &arr2[N - 1]);
  97. 		qsort(arr2, N, sizeof(int), compare);
  98. 		EndTime = chrono::system_clock::now();
  99. 		micro = chrono::duration_cast<chrono::microseconds>(EndTime - StartTime);
  100. 		cout << "qsort Function : " << micro.count() << "μs" << endl;
  101.  
  102. 		print(arr, n);
  103. 		//print(arr2, n);
  104. 	}
  105.  
  106. 	return 0;
  107. }
  108.  
  109.  
  110.  
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:85:34: error: 'memcpy' was not declared in this scope
   memcpy(arr2, arr, sizeof(int)*N);
                                  ^
stdout
copy 
Standard output is empty
https://ideone.com/cvpXmI
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!