fork download
copy 
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <algorithm>
  4. #include <random>
  5. #include <x86intrin.h>
  6.  
  7. void radix(unsigned sdv,int* a,int* b){
  8.  
  9. 	constexpr unsigned mask=0xff;
  10. 	unsigned mk[256]={};
  11. 	int *pk[256],temp;
  12.  
  13. 	for (int* i=a;i<b;i++){
  14. 		mk[(*i>>sdv)&mask]++;
  15. 	}
  16. 	pk[0]=a;
  17. 	for (int i=1;i<256;i++)
  18. 		pk[i]=pk[i-1]+mk[i-1];
  19. 	for (unsigned i=0;i<256;i++)
  20. 	{
  21. 		while (mk[i]>0){
  22. 			temp=*pk[i];
  23. 			unsigned y=((temp)>>sdv)&mask;
  24. 			while (y!=i){
  25. 				std::swap(temp,*pk[y]);
  26. 				pk[y]++;
  27. 				mk[y]--;
  28. 				y=((temp)>>sdv)&mask;
  29. 			}
  30. 			*pk[i]=temp;
  31. 			pk[i]++;
  32. 			mk[i]--;
  33. 		}
  34. 	};
  35. 	if (sdv==0)
  36. 		return;
  37.  
  38. 	if (unsigned r=(pk[0]-a);r<48*(1+(sdv>>3))){
  39. 		std::sort(a,pk[0]);
  40. 	}
  41. 	else
  42. 		radix(sdv-8,a,pk[0]);
  43. 	for (unsigned i=1;i<256;i++){
  44. 		if (unsigned r=(pk[i]-pk[i-1]);r<48*(1+(sdv>>3))){
  45. 			std::sort(pk[i-1],pk[i]);
  46. 		}
  47. 		else radix(sdv-8,pk[i-1],pk[i]);
  48. 	}
  49.  
  50. }
  51.  
  52. void test(unsigned n,bool use_radix=false){
  53. 	std::default_random_engine gen(_rdtsc());
  54. 	std::uniform_int_distribution<int> ds(-2147483648,2147483647);
  55. 	std::vector<int> arr(n);
  56. 	for (unsigned i=0;i<n;i++)//заполнение случайными
  57. 		arr[i]=ds(gen);
  58.  
  59. 	unsigned t1,t2;
  60.  
  61. 	if (use_radix){
  62. 		t1=clock();
  63. 		radix(24,arr.data(),arr.data()+arr.size());
  64. 		t2=clock();
  65. 		printf("radix sort %d in %.3f ms\n",n,1.0e3*double(t2-t1)/CLOCKS_PER_SEC);
  66. 	}else{
  67. 		t1=clock();
  68. 		std::sort(arr.begin(),arr.end());
  69. 		t2=clock();
  70. 		printf("std sort %d in %.3f ms\n",n,1.0e3*double(t2-t1)/CLOCKS_PER_SEC);
  71. 	}
  72.  
  73.  
  74. }
  75.  
  76. int main()
  77. {
  78. 	test(100000);
  79. 	test(1000000);
  80. 	test(10000000);
  81. 	test(100000,true);
  82. 	test(1000000,true);
  83. 	test(10000000,true);
  84. }
  85.  
Success #stdin #stdout 1.9s 45720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
std sort 100000 in 5.223 ms
std sort 1000000 in 54.504 ms
std sort 10000000 in 693.762 ms
radix sort 100000 in 1.816 ms
radix sort 1000000 in 20.134 ms
radix sort 10000000 in 358.734 ms
https://ideone.com/MLZQee
language:
C++14 (clang 8.0)
created:
5 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!