fork(1) download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <stdint.h>
  4. #include <inttypes.h>
  5.  
  6. typedef union {
  7. 	struct {
  8. 		uint32_t c8[256];
  9. 		uint32_t c7[256];
  10. 		uint32_t c6[256];
  11. 		uint32_t c5[256];
  12. 		uint32_t c4[256];
  13. 		uint32_t c3[256];
  14. 		uint32_t c2[256];
  15. 		uint32_t c1[256];
  16. 	};
  17. 	uint32_t counts[256 * 8];
  18. } rscounts_t;
  19.  
  20. uint64_t * radixSort(uint64_t * array, uint32_t size) {
  21. 	rscounts_t counts;
  22. 	memset(&counts, 0, 256 * 8 * sizeof(uint32_t));
  23. 	uint64_t * cpy = (uint64_t *)malloc(size * sizeof(uint64_t));
  24. 	uint32_t o8=0, o7=0, o6=0, o5=0, o4=0, o3=0, o2=0, o1=0;
  25. 	uint32_t t8, t7, t6, t5, t4, t3, t2, t1;
  26. 	uint32_t x;
  27. 	// calculate counts
  28. 	for(x = 0; x < size; x++) {
  29. 		t8 = array[x] & 0xff;
  30. 		t7 = (array[x] >> 8) & 0xff;
  31. 		t6 = (array[x] >> 16) & 0xff;
  32. 		t5 = (array[x] >> 24) & 0xff;
  33. 		t4 = (array[x] >> 32) & 0xff;
  34. 		t3 = (array[x] >> 40) & 0xff;
  35. 		t2 = (array[x] >> 48) & 0xff;
  36. 		t1 = (array[x] >> 56) & 0xff;
  37. 		counts.c8[t8]++;
  38. 		counts.c7[t7]++;
  39. 		counts.c6[t6]++;
  40. 		counts.c5[t5]++;
  41. 		counts.c4[t4]++;
  42. 		counts.c3[t3]++;
  43. 		counts.c2[t2]++;
  44. 		counts.c1[t1]++;
  45. 	}
  46. 	// convert counts to offsets
  47. 	for(x = 0; x < 256; x++) {
  48. 		t8 = o8 + counts.c8[x];
  49. 		t7 = o7 + counts.c7[x];
  50. 		t6 = o6 + counts.c6[x];
  51. 		t5 = o5 + counts.c5[x];
  52. 		t4 = o4 + counts.c4[x];
  53. 		t3 = o3 + counts.c3[x];
  54. 		t2 = o2 + counts.c2[x];
  55. 		t1 = o1 + counts.c1[x];
  56. 		counts.c8[x] = o8;
  57. 		counts.c7[x] = o7;
  58. 		counts.c6[x] = o6;
  59. 		counts.c5[x] = o5;
  60. 		counts.c4[x] = o4;
  61. 		counts.c3[x] = o3;
  62. 		counts.c2[x] = o2;
  63. 		counts.c1[x] = o1;
  64. 		o8 = t8; 
  65. 		o7 = t7; 
  66. 		o6 = t6; 
  67. 		o5 = t5; 
  68. 		o4 = t4; 
  69. 		o3 = t3; 
  70. 		o2 = t2; 
  71. 		o1 = t1;
  72. 	}
  73. 	// radix
  74. 	for(x = 0; x < size; x++) {
  75. 		t8 = array[x] & 0xff;
  76. 		cpy[counts.c8[t8]] = array[x];
  77. 		counts.c8[t8]++;
  78. 	}
  79. 	for(x = 0; x < size; x++) {
  80. 		t7 = (cpy[x] >> 8) & 0xff;
  81. 		array[counts.c7[t7]] = cpy[x];
  82. 		counts.c7[t7]++;
  83. 	}
  84. 	for(x = 0; x < size; x++) {
  85. 		t6 = (array[x] >> 16) & 0xff;
  86. 		cpy[counts.c6[t6]] = array[x];
  87. 		counts.c6[t6]++;
  88. 	}
  89. 	for(x = 0; x < size; x++) {
  90. 		t5 = (cpy[x] >> 24) & 0xff;
  91. 		array[counts.c5[t5]] = cpy[x];
  92. 		counts.c5[t5]++;
  93. 	}
  94. 	for(x = 0; x < size; x++) {
  95. 		t4 = (array[x] >> 32) & 0xff;
  96. 		cpy[counts.c4[t4]] = array[x];
  97. 		counts.c4[t4]++;
  98. 	}
  99. 	for(x = 0; x < size; x++) {
  100. 		t3 = (cpy[x] >> 40) & 0xff;
  101. 		array[counts.c3[t3]] = cpy[x];
  102. 		counts.c3[t3]++;
  103. 	}
  104. 	for(x = 0; x < size; x++) {
  105. 		t2 = (array[x] >> 48) & 0xff;
  106. 		cpy[counts.c2[t2]] = array[x];
  107. 		counts.c2[t2]++;
  108. 	}
  109. 	for(x = 0; x < size; x++) {
  110. 		t1 = (cpy[x] >> 56) & 0xff;
  111. 		array[counts.c1[t1]] = cpy[x];
  112. 		counts.c1[t1]++;
  113. 	}
  114. 	free(cpy);
  115. 	return array;
  116. }
  117. int main(void) {
  118. 	uint32_t size = 1000;
  119. 	uint32_t x;
  120. 	uint64_t * array = (uint64_t *)malloc(size * sizeof(uint64_t));
  121. 	for(x = 0; x < size; x++) {
  122. 		array[x] = size - x;
  123. 	}
  124. 	printf("%" PRIu64 ", %" PRIu64 "\n", array[0], array[size - 1]);
  125. 	array = radixSort(array, size);
  126. 	printf("%" PRIu64 ", %" PRIu64 "\n", array[0], array[size - 1]);
  127. 	return 0;
  128. }
  129.  
Success #stdin #stdout 0s 2292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000, 1
1, 1000
https://ideone.com/JHI0d9
language:
C (gcc 8.3)
created:
8 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!