fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <ctime>
  5. #include <type_traits>
  6. using namespace std;
  7. #define N 10
  8.  
  9. template <typename T>
  10. void PrintArray(const std::vector<T>& myArray)
  11. {
  12. 	for (auto&& element : myArray)
  13. 	{
  14. 		std::cout << element << std::endl;
  15. 	}
  16. }
  17.  
  18. template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
  19. void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
  20. {
  21. 	if (zerosEnd+1 >= onesBegin-1 || mask == 0) 
  22. 		return;
  23.  
  24. 	int zerosEnd2 = zerosEnd;
  25. 	int onesBegin2 = onesBegin;
  26. 	while(zerosEnd2+1 <= onesBegin2-1)
  27. 	{
  28. 		// swap ones to the right
  29. 		// remember to invert if negative
  30. 		if (
  31. 			((myArray[zerosEnd2+1] >= 0 ? myArray[zerosEnd2+1] : -1 * (myArray[zerosEnd2+1]))
  32. 			& mask) != 0
  33. 		)
  34. 		{
  35. 			std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
  36. 			--onesBegin2;
  37. 		}
  38. 		else
  39. 		{
  40. 			++zerosEnd2;
  41. 		}
  42. 	}
  43.  
  44. 	mask >>= 1;
  45.  
  46. 	//recurse on lhs
  47. 	RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);
  48.  
  49. 	//recurse on rhs
  50. 	RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
  51.  
  52. }
  53.  
  54. template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
  55. void InPlaceRadixSort(std::vector<T>& myArray)
  56. {
  57. 	int zerosEnd = -1;
  58. 	int onesBegin = static_cast<int>(myArray.size());
  59. 	T mask = static_cast<T>(1) << sizeof(T)*8-1;
  60. 	while(zerosEnd+1 <= onesBegin-1)
  61. 	{
  62. 		if (
  63. 			(myArray[zerosEnd+1] >= static_cast<T>(0) ? myArray[zerosEnd+1] : 
  64. 			static_cast<T>(-1) * myArray[zerosEnd+1]
  65. 			& mask) != 0
  66. 		)
  67. 		{
  68. 			std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
  69. 			--onesBegin;
  70. 		}
  71. 		else
  72. 		{
  73. 			++zerosEnd;
  74. 		}
  75. 	}
  76. 	mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
  77. 	//recurse on lhs
  78. 	RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
  79. 	//recurse on rhs
  80. 	RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));
  81. }
  82.  
  83. int main() {
  84. 	srand(time(NULL));
  85. 	std::vector<int> myArray(N);
  86. 	for (size_t i=0;i<myArray.size();++i)
  87. 	{
  88. 		myArray[i] = rand() % 100 * (rand() % 2 == 1?-1:1);
  89. 	}
  90.  
  91. 	std::cout << "Vector before radix sort: " << std::endl;
  92. 	PrintArray(myArray);
  93. 	InPlaceRadixSort(myArray);
  94. 	std::cout << "Vector after radix sort: " << std::endl;
  95. 	PrintArray(myArray);
  96.  
  97. 	for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
  98. 	{
  99. 		if (myArray[i] == myArray[j])
  100. 		{
  101. 			std::cout << "Found duplicate element " << myArray[i];
  102. 		}
  103. 	}
  104. 	return 0;
  105. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Vector before radix sort: 
42
32
92
-38
-79
-81
30
-35
45
-79
Vector after radix sort: 
-35
-38
-79
-79
-81
30
32
42
45
92
Found duplicate element -79
https://ideone.com/5K8VCn
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!