fork(1) download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <climits>
  4. #include <functional>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <iterator>
  8. #include <random>
  9. #include <stdexcept>
  10. #include <type_traits>
  11. #include <string>
  12. #include <cstdlib>
  13. #include <ctime>
  14. #include <vector>
  15.  
  16.  
  17. template<class bidi_iterator, class predicate>
  18. void quick_sort(const bidi_iterator first, const bidi_iterator last, const predicate& pred) {
  19. 	using std::swap;
  20.     using namespace std::placeholders;
  21. 	if (first == last) //0
  22. 		return;
  23. 	bidi_iterator next = std::next(first);
  24. 	if (next == last)  // 1
  25. 		return;
  26. 	if (std::next(next) == last) { // 2 
  27. 		if (pred(*next, *first))
  28. 			swap(*first, *next);
  29. 		return;
  30. 	}
  31. 	//3+
  32. 	bidi_iterator mid = std::partition(next, last, std::bind(pred, _1, std::cref(*first)));
  33. 	bidi_iterator prev = std::prev(mid);
  34.     swap(*first, *prev);
  35. 	if (next!=mid && next!=prev) //2+ on left
  36. 		quick_sort(first, prev, pred);
  37. 	if (mid!=last && mid!=std::prev(last)) //2+ on right
  38. 		quick_sort(mid, last, pred);
  39. 	assert(std::is_sorted(first, last, pred));
  40. }
  41. template<class bidi_iterator>
  42. void quick_sort(const bidi_iterator first, const bidi_iterator last) {
  43. 	typedef typename std::iterator_traits<bidi_iterator>::value_type value_type;
  44. 	return quick_sort(first, last, std::less<value_type>());
  45. }
  46.  
  47. template<class bidi_iterator, class predicate>
  48. void inplace_sort(const bidi_iterator first, const bidi_iterator last, const predicate& pred) {
  49. 	using std::swap;
  50.     using namespace std::placeholders;
  51. 	bidi_iterator beginchunk = first;
  52. 	bidi_iterator unorganized = first;
  53. 	bidi_iterator endchunk = first;
  54. 	//while there's more to do
  55. 	while(beginchunk != last) {
  56. 		//if we haven't yet organized any data
  57. 		if (beginchunk == unorganized) {
  58. 			//then begin points at our new pivot
  59. 			bidi_iterator n(std::next(beginchunk));
  60.             if (n == last) return;
  61. 			//partition everything from here to the end of the data
  62. 			//mark the right side as completely unorganized
  63. 			unorganized = std::partition(n, last, std::bind(pred, _1, std::cref(*beginchunk)));
  64. 			//and now that the left side is partially organized 
  65. 			//as a pivot followed by all unsorted elements less than the pivot
  66. 			//if there's more then one on the left, we "recurse" down the left.
  67. 			if (unorganized != n)
  68. 				endchunk = unorganized;
  69. 			//otherwise, "recurse" down the right
  70. 			else {
  71. 				beginchunk = unorganized;
  72. 				continue;
  73. 			}
  74. 		}
  75. 		//if we don't yet know where the end of those unsorted elements are, we'll have to find them
  76. 		if (beginchunk == endchunk) {
  77. 			++endchunk;
  78. 			//if some are already sorted, skip them
  79. 			while(endchunk!=unorganized && pred(*beginchunk, *endchunk)) {
  80. 				++beginchunk;
  81. 				++endchunk;
  82. 			}
  83. 			//if sorted all the way to the unorganized, jump up to that bit
  84. 			if (endchunk == unorganized) {
  85. 				beginchunk = unorganized;
  86. 				continue;
  87. 			}
  88. 			//if we got this far, that means we found a pivot followed by one less than the pivot
  89. 			++endchunk;
  90. 			//data was already organized as a pivot followed by the unsorted elements less than that pivot
  91. 			//so we find the next element that's greater than the pivot
  92. 			while(endchunk!=unorganized && pred(*endchunk, *beginchunk))
  93. 				++endchunk;
  94. 		}
  95. 		//beginchunk points at the old pivot
  96. 		//so n points at the first element in this chunk, which will be our new pivot
  97. 		bidi_iterator n(std::next(beginchunk));
  98.         if (n != endchunk) {
  99. 			//so we'll partition the data after the new pivot
  100. 			bidi_iterator nn(std::next(n));
  101. 			//if there's more than two elements in the chunk
  102. 			if (nn != endchunk) {
  103. 				//then we partition!  
  104. 				bidi_iterator midchunk = std::partition(nn, endchunk, std::bind(pred, _1, std::cref(*n)));
  105. 				//here's the tricky part:
  106. 				//this chunk was the old pivot followed by the unsorted elements less than it.
  107. 				//we have to move the old pivot to between the two paritions we just now made
  108.                 bidi_iterator prev(std::prev(midchunk));
  109. 				swap(*beginchunk, *prev);
  110. 				//and move the new pivot to the beginning of the first chunk
  111. 				//which devides this into two chunks.  Those less than the new pivot, and those less than the new
  112. 				//which are preceeded by the new pivot and the old pivot respectively
  113. 				//this allows us to detect the boundaries of both chunks
  114. 				if (n != prev) {
  115. 					swap(*beginchunk, *n);
  116. 					//finally, we'll "recurse" on the left chunk
  117. 					endchunk = prev;
  118. 				} else {
  119. 					//unless there was no elements less than the new pivot
  120. 					//then we "recuse" down the right insead
  121. 					beginchunk = n;
  122. 				}
  123. 			//oh, if there were only two elements in the chunk, then we just swap them
  124. 			} else {
  125. 				swap(*beginchunk, *n);
  126. 				//and we don't know what's to the right, we'll discover that 
  127. 				//at the beginning of the next iteration;
  128. 				beginchunk = nn;
  129. 				endchunk = beginchunk;
  130. 			}
  131.         } else {
  132.             ++beginchunk;
  133.         }
  134. 	}
  135. }
  136. template<class bidi_iterator>
  137. void inplace_sort(bidi_iterator begin, bidi_iterator end) {
  138. 	typedef typename std::iterator_traits<bidi_iterator>::value_type value_type;
  139. 	return inplace_sort(begin, end, std::less<value_type>());
  140. }
  141.  
  142. //tracer class used to track comparisons and swaps
  143. //other numbers aren't used in this test
  144. template <typename T>
  145. struct tracer {
  146. 	T value; 
  147.     tracer() :value() {++default_construct_count;}
  148.     tracer(const tracer& rhs) :value(rhs.value) {++copy_construct_count;}
  149.     //template<class U> tracer(std::enable_if<std::is_convertible<U, T>::value, const U&>::type v) :value(v) {++conversion_construct_count;}
  150.     template<class U> tracer(const U& v) :value(v) {++conversion_construct_count;}
  151.     ~tracer() {++destructor_count;}
  152. 	tracer& operator=(const tracer& rhs) { value = rhs.value; ++copy_assign_count; return *this; }
  153.     //template<class U> tracer<T>& operator=(std::enable_if<std::is_convertible<U, T>::value, const U&>::type v) { value = v; ++conversion_assign_count; return *this; }
  154.     template<class U> tracer<T>& operator=(const U& v) { value = v; ++conversion_assign_count; return *this; }
  155.  
  156.     static unsigned long long default_construct_count;
  157.     static unsigned long long copy_construct_count;
  158.     static unsigned long long conversion_construct_count;
  159.     static unsigned long long compare_count;
  160. 	static unsigned long long swap_count;
  161. 	static unsigned long long copy_assign_count;
  162. 	static unsigned long long conversion_assign_count;
  163. 	static unsigned long long destructor_count;
  164. };
  165. template<class T>
  166. void reset_counts(tracer<T>)  {
  167.     tracer<T>::default_construct_count = 0;
  168.     tracer<T>::copy_construct_count = 0;
  169.     tracer<T>::conversion_construct_count = 0;
  170. 	tracer<T>::compare_count = 0;
  171. 	tracer<T>::swap_count = 0;
  172. 	tracer<T>::copy_assign_count = 0;
  173.     tracer<T>::conversion_assign_count = 0;
  174.     tracer<T>::destructor_count = 0;
  175. }
  176. template<class T>
  177. void show_counts(tracer<T>)  {
  178. 	std::cout << std::setw(10) << tracer<T>::compare_count << ' ';
  179. 	std::cout << std::setw(10) << tracer<T>::swap_count << ' ';
  180. }
  181. template <typename T>
  182. bool operator<(const tracer<T>& lhs, const tracer<T>& rhs)
  183. { ++tracer<T>::compare_count;return std::less<T>()(lhs.value,rhs.value);}
  184. template <typename T>
  185. void swap(tracer<T>& lhs, tracer<T>& rhs) 
  186. {using std::swap;swap(lhs.value, rhs.value);++tracer<T>::swap_count;}
  187. template <typename T>
  188. std::ostream& operator<<(std::ostream& stream, const tracer<T>& obj)
  189. { return stream << obj.value;}
  190. template <typename T> unsigned long long tracer<T>::default_construct_count = 0;
  191. template <typename T> unsigned long long tracer<T>::copy_construct_count = 0;
  192. template <typename T> unsigned long long tracer<T>::conversion_construct_count = 0;
  193. template <typename T> unsigned long long tracer<T>::compare_count = 0;
  194. template <typename T> unsigned long long tracer<T>::swap_count = 0;
  195. template <typename T> unsigned long long tracer<T>::copy_assign_count = 0;
  196. template <typename T> unsigned long long tracer<T>::conversion_assign_count = 0;
  197. template <typename T> unsigned long long tracer<T>::destructor_count = 0;
  198. void reset_counts(int)  {}
  199. void reset_counts(std::string)  {}
  200. void show_counts(int)  {
  201.     std::cout << std::setw(10) << '?' << ' ';
  202. 	std::cout << std::setw(10) << '?' << ' ';
  203. }
  204. void show_counts(std::string)  {
  205. 	std::cout << std::setw(10) << '?' << ' ';
  206. 	std::cout << std::setw(10) << '?' << ' ';
  207. }
  208.  
  209. void hardcoded_tests() {
  210.     std::cout << "Beginning accuracy tests\n";
  211.     std::vector<int> t;
  212.     inplace_sort(t.begin(), t.end());
  213.     bool pass = std::is_sorted(t.begin(), t.end());
  214.     assert(pass);
  215.     //for all lengths of data from 1 to 7 inclusive
  216.     for(unsigned len=1; pass && len<8; ++len) {
  217.         std::vector<int> data(len, 0);
  218.         unsigned max = 1<<(len-1);
  219.         //for each pattern of increases or not-increases
  220.         //because {1,3,3} and {1,2,2} are effectively the same test
  221.         for(unsigned bits=0; pass && bits<max; ++bits) {
  222.             for(unsigned i=0; i<len-1; ++i) {
  223.                 int v = (bits & (1<<i)) >> i;
  224.                 data[i+1] = data[i] + v;
  225.             }
  226.             //test all permutations of that pattern
  227.             do {
  228.                 t = data;
  229.                 inplace_sort(t.begin(), t.end());
  230.                 pass = std::is_sorted(t.begin(), t.end());
  231.                 assert(pass);
  232.             } while(pass && std::next_permutation(data.begin(), data.end()));
  233.         }
  234.     }
  235.     if (pass) std::cout << "Passed all accuracy tests" << std::endl;
  236.     else {
  237.         std::cout << "Failed on {";
  238.         for(unsigned i=0; i<t.size(); ++i) {
  239.             if (i!=0) std::cout << ' ';
  240.             std::cout << t[i];
  241.         }
  242.         std::cout << "}" << std::endl;
  243.     }
  244. }
  245.  
  246. template<class type, class generator>
  247. void timing_tests(generator& gen, const char* name_of_type ) {
  248.     std::cout << "Beginning timing tests with " << name_of_type << "\n";
  249. 	std::cout << "name              N      comps      swaps      ticks\n";
  250.     const unsigned test_size=2097152;
  251. 	//clock_t stop = clock() + CLOCKS_PER_SEC/4; //.25
  252. 	//for(unsigned test_size=32; test_size<=INT_MAX && clock()<stop; test_size*=2) 
  253.     {    
  254. 		clock_t sort_time=0;
  255. 		std::vector<type> data(test_size);
  256. 		for(unsigned i=0; i<data.size(); ++i)
  257. 			data[i] = gen();
  258. 		std::vector<type> data2;
  259.  
  260. 		std::cout << "quick    " << std::setw(10) << test_size << ' ' << std::flush;
  261. 		data2 = data;
  262. 		quick_sort(data2.begin(), data2.end());
  263.         assert(std::is_sorted(data2.begin(), data2.end()));
  264. 		data2 = data;
  265. 		reset_counts(data[0]);
  266. 		clock_t begin = clock();
  267. 		quick_sort(data2.begin(), data2.end());
  268. 		sort_time = clock()-begin;
  269. 		show_counts(data[0]);
  270. 		std::cout << std::setw(10) << sort_time << std::endl;
  271.  
  272. 		std::cout << "inplace  " << std::setw(10) << test_size << ' ' << std::flush;
  273. 		data2 = data;
  274. 		inplace_sort(data2.begin(), data2.end());
  275.         assert(std::is_sorted(data2.begin(), data2.end()));
  276. 		data2 = data;
  277. 		reset_counts(data[0]);
  278. 		begin = clock();
  279. 		inplace_sort(data2.begin(), data2.end());
  280. 		sort_time = clock()-begin;
  281. 		show_counts(data[0]);
  282. 		std::cout << std::setw(10) << sort_time << std::endl;
  283. 	}
  284.     std::cout << "Finished timing tests\n";
  285. }
  286.  
  287. struct randstring {
  288. 	randstring(unsigned len, std::mt19937& generator) 
  289. 		:l(len), gen(&generator), dist(CHAR_MIN,CHAR_MAX) {}
  290. 	std::string operator()() {
  291. 		std::string r(l, '\0');
  292. 		for(unsigned i=0; i<l; ++i)
  293. 			r[i] = (char)dist(*gen);
  294. 		return r;
  295. 	}
  296. 	unsigned l;
  297. 	std::mt19937* gen;
  298. 	std::uniform_int_distribution<int> dist;
  299. };
  300.  
  301. int main() {
  302.     srand(time(NULL));
  303.     std::mt19937 gen(rand());
  304. 	std::uniform_int_distribution<int> dist(INT_MIN, INT_MAX);
  305. 	auto intrng = std::bind(dist, gen);
  306. 	randstring strrng(17u, gen);
  307.  
  308.     hardcoded_tests();
  309.     timing_tests<tracer<int>>(intrng, "tracer<int>");
  310.     timing_tests<int>(intrng, "int");
  311.     timing_tests<std::string>(strrng, "string");
  312. 	return 0;
  313. }
  314.  
Time limit exceeded #stdin #stdout 5s 60600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Beginning accuracy tests
Passed all accuracy tests
Beginning timing tests with tracer<int>
name              N      comps      swaps      ticks
quick       2097152  104822137   10253297     440000
inplace     2097152   78569130   12108783     410000
Finished timing tests
Beginning timing tests with int
name              N      comps      swaps      ticks
quick       2097152          ?          ?     350000
inplace     2097152          ?          ?     280000
https://ideone.com/cv6VsT
language:
C++14 (gcc 8.3)
created:
11 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!