fork download
  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
stdin
Standard input is empty
stdout
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