fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. #include <type_traits>
  5.  
  6. template <typename It>
  7. It radix_sort_recurse(It start, It stop, unsigned bit, unsigned last_bit) {
  8. 	if(start == stop)
  9. 		return stop;
  10. 	const unsigned bitmask = 1 << bit;
  11. 	It left = start;
  12. 	It right = stop;
  13. 	right--; //make right point to a valid element
  14. 	//loop until all elements have been partitioned
  15. 	//afterwards left will point AFTER the last left element
  16. 	while(left <= right) {
  17. 		if(*left & bitmask) std::swap(*left, *right--);
  18. 		else                left++;
  19. 	}
  20. 	//recurse on left and right partitions
  21. 	if(bit > last_bit) {
  22. 		radix_sort_recurse(start, left, bit-1, last_bit);
  23. 		radix_sort_recurse(left,  stop, bit-1, last_bit);
  24. 	}
  25. 	return left;
  26. }
  27.  
  28.  
  29. template <typename It>
  30. void radix_parity_sort(It start, It stop) {
  31. 	using int_t = typename std::remove_reference<decltype(*start)>::type;
  32. 	//count the bits
  33. 	constexpr auto digits = std::numeric_limits<int_t>::digits;
  34. 	constexpr auto bits = digits + std::is_signed<int_t>::value; 
  35.  
  36. 	//partition based on parity
  37. 	auto p = radix_sort_recurse(start, stop, 0, 0);
  38.  
  39. 	//msb radix sort on rest of bits
  40. 	radix_sort_recurse(start, p,    bits-1, 1);
  41. 	radix_sort_recurse(p,     stop, bits-1, 1);
  42. }
  43.  
  44. int main() {
  45. 	std::vector<int> v = {
  46. 		43, 380, 246, 807, 510, 433, 878, 78, 789, 103, 492, 543, 895,
  47. 		439, 466, 199, 614, 867, 3, 458, 953, 554, 561, 501, 324, 859,
  48. 		636, 768, 251, 201, 305, 435, 790, 357, 55, 739, 751, 704, 408,
  49. 		665, 104, 86, 255, 46, 103, 311, 265, 85, 155, 794, 704, 56,
  50. 		909, 783, 892, 562, 289, 805, 400, 394, 541, 959, 335, 263, 2,
  51. 		57, 999, 9, 450, 696, 341, 521, 137, 448, 454, 411, 144, 773,
  52. 		750, 821, 711, 926, 224, 882, 717, 157, 488, 26, 126, 945, 710,
  53. 		702, 29, 109, 301, 176, 382, 46, 175, 360
  54. 	};
  55. 	radix_parity_sort(v.begin(), v.end());
  56. 	for(auto e : v)
  57. 		std::cout << e << " ";
  58. 	std::cout << "\n";
  59. }
Success #stdin #stdout 0s 3228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 26 46 46 56 78 86 104 126 144 176 224 246 324 360 380 382 394 400 408 448 450 454 458 466 488 492 510 554 562 614 636 696 702 704 704 710 750 768 790 794 878 882 892 926 3 9 29 43 55 57 85 103 103 109 137 155 157 175 199 201 251 255 263 265 289 301 305 311 335 341 357 411 433 435 439 501 521 541 543 561 665 711 717 739 751 773 783 789 805 807 821 859 867 895 909 945 953 959 999
https://ideone.com/FdvF0M
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!