fork download
copy 
  1. #include <algorithm>
  2. #include <functional>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <cassert>
  6.  
  7. //naive quicksort
  8. template<class bidi_iterator, class predicate>
  9. void quick_sort(const bidi_iterator first, const bidi_iterator last, const predicate& pred) {
  10. 	using std::swap;
  11. 	if (first == last) //0
  12. 		return;
  13. 	bidi_iterator next = std::next(first);
  14. 	if (next == last)  // 1
  15. 		return;
  16. 	if (std::next(next) == last) { // 2 
  17. 		if (pred(*next, *first))
  18. 			swap(*first, *next);
  19. 		return;
  20. 	}
  21. 	//3+
  22. 	bidi_iterator mid = std::partition(next, last, std::bind2nd(pred, *first));
  23. 	if (mid!=next) { //1+ on left
  24. 		bidi_iterator prev = std::prev(mid);
  25. 		swap(*first, *prev);
  26. 		if (std::next(next)!=mid) //2+ on left
  27. 			quick_sort(first, prev, pred);
  28. 	}
  29. 	if (mid!=last && mid!=std::prev(last)) //2+ on right
  30. 		quick_sort(mid, last, pred);
  31. 	assert(std::is_sorted(first, last, pred));
  32. }
  33. template<class bidi_iterator>
  34. void quick_sort(const bidi_iterator first, const bidi_iterator last) {
  35. 	typedef typename std::iterator_traits<bidi_iterator>::value_type value_type;
  36. 	return quick_sort(first, last, std::less<value_type>());
  37. }
  38.  
  39. //inplace quicksort
  40. //This sort needs to work on a series of "chunks" in a certain format.
  41. // Each chunk is: [(1)pivot][(?) data less than pivot, but greater than pivot of previous chunk]
  42. //     Given data:  17,16,8,6,18,12,14,13,8,6,5,19,22,12,16,20,7,0,10,6,15,18,19,6
  43. //     We chunk it: [17,16,8,6,6,12,14,13,8,6,5,15,6,12,16,10,7,0],[20,18,19,18,19],[22]
  44. // Then we iterate over the list, one chunk at a time:  [17,16,8,6,6,12,14,13,8,6,5,15,6,12,16,10,7,0]
  45. //    splitting each chunk into two subchunks: [16,7,8,6,6,12,14,13,8,6,5,15,6,12,0,10],[17,16,]
  46. // A chunk that is 1 element (only the pivot, no data) is in the correct location.
  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 std::distance;
  51. 	if (first == last)
  52. 		return;
  53. 	bidi_iterator beginchunk = first;
  54. 	bidi_iterator endchunk = last;
  55. 	bool cached_end = true;
  56. 	//Rearrange the origional data into "Chunks"
  57. 	//Basically, just quicksort down the right side until we find the biggest element
  58. 	do {
  59. 		bidi_iterator mid = std::partition(std::next(beginchunk), last, std::bind2nd(pred, *beginchunk));
  60. 		if (beginchunk == first)  //cache first chunk size
  61. 			endchunk = mid;
  62. 		beginchunk = mid;
  63. 	} while(beginchunk != last);
  64. 	beginchunk = first; //starting from the left
  65. 	do {
  66. 		//find first unsorted chunk (first consecutive unsorted elements)
  67. 		bidi_iterator newpivot = std::next(beginchunk);
  68. 		while(newpivot!=last && pred(*beginchunk, *newpivot)) {
  69. 			beginchunk = newpivot; 
  70. 			++newpivot;
  71. 			cached_end = false;
  72. 		}
  73. 		//if it's all sorted, we're done
  74. 		if (newpivot==last) 
  75. 			break;
  76. 		if (cached_end == false) {
  77. 			//find the end of the chunk (first element greater than *beginchunk)
  78. 			endchunk = std::next(newpivot);
  79. 			int len = 2;
  80. 			while(endchunk!=last && pred(*endchunk, *beginchunk)) {
  81. 				++len;
  82. 				++endchunk;
  83. 			}
  84. 		}
  85. 		bidi_iterator mid =endchunk;
  86. 		// if the chunk is two elements, just swap
  87. 		if (std::next(newpivot) == endchunk) {
  88. 			swap(*beginchunk, *newpivot);	
  89. 			beginchunk = endchunk; //move to the next chunk
  90. 			cached_end = false;
  91. 		} else { 
  92. 			//if more than two, partition into two seperate chunks
  93. 			//first, parition on newpivot (the first element)
  94. 			mid = std::partition(std::next(newpivot), endchunk, std::bind2nd(pred, *newpivot));	
  95. 			//this means we have to move the pivots
  96. 			//so the newpivot pivot begins the first subchunk
  97. 			//and the beginchunk pivot begins the second subchunk
  98. 			swap(*beginchunk, *newpivot);
  99. 			bidi_iterator prev = std::prev(mid);
  100. 			if (newpivot != prev) {
  101. 				swap(*newpivot, *prev);
  102. 				//and cached the endchunk since we know it already
  103. 				endchunk = mid;
  104. 				cached_end = true;
  105. 			} else
  106. 				cached_end = false;
  107. 			//and "repeat" which will do the left side
  108. 		}
  109. 	} while(beginchunk != last);
  110. 	assert(std::is_sorted(first, last, pred));
  111. 	return;
  112. }
  113.  
  114. template<class bidi_iterator>
  115. void inplace_sort(bidi_iterator begin, bidi_iterator end) {
  116. 	typedef typename std::iterator_traits<bidi_iterator>::value_type value_type;
  117. 	return inplace_sort(begin, end, std::less<value_type>());
  118. }
  119.  
  120. #include <cstdlib>
  121. #include <ctime>
  122. #include <vector>
  123.  
  124. template <typename T>
  125. struct tracer : std::less<T> {
  126.     static unsigned count;
  127.  
  128.     bool operator()(T x, T y) const {
  129.         ++count;
  130.         return std::less<T>::operator()(x, y);
  131.     }
  132. };
  133. template <typename T>
  134. unsigned tracer<T>::count = 0;
  135.  
  136. int main() {
  137.         unsigned test_size;
  138.         while(std::cin >> test_size) { 
  139. 			double stdsort_time=0;
  140. 			double inplacesort_time=0;
  141. 			srand((unsigned)time(NULL));
  142. 			std::vector<int> data(test_size);
  143. 			for(unsigned i=0; i<data.size(); ++i)
  144. 					data[i] = 10000+rand();
  145. 			std::vector<int> data2;
  146. 			{
  147. 					data2 = data;
  148. 					std::sort(data2.begin(), data2.end(), tracer<int>());
  149. 					data2 = data;
  150. 					clock_t begin = clock();
  151. 					std::sort(data2.begin(), data2.end());
  152. 					clock_t end = clock();
  153. 					stdsort_time = double(end-begin)/CLOCKS_PER_SEC;
  154. 			}
  155. 			std::cout << "comparisons: " << tracer<int>::count << ' ';
  156. 			std::cout << "std::sort    took " << stdsort_time << "s.\n";
  157. 			tracer<int>::count = 0;
  158. 			{
  159. 					data2 = data;
  160. 					quick_sort(data2.begin(), data2.end(), tracer<int>());
  161. 					data2 = data;
  162. 					clock_t begin = clock();
  163. 					quick_sort(data2.begin(), data2.end());
  164. 					clock_t end = clock();
  165. 					stdsort_time = double(end-begin)/CLOCKS_PER_SEC;
  166. 			}
  167. 			std::cout << "comparisons: " << tracer<int>::count << ' ';
  168. 			std::cout << "quicksort    took " << stdsort_time << "s.\n";
  169. 			tracer<int>::count = 0;
  170. 			{
  171. 					data2 = data;
  172. 					inplace_sort(data2.begin(), data2.end(), tracer<int>());
  173. 					data2 = data;
  174. 					clock_t begin = clock();
  175. 					inplace_sort(data2.begin(), data2.end());
  176. 					clock_t end = clock();
  177. 					inplacesort_time = double(end-begin)/CLOCKS_PER_SEC;
  178. 			}
  179. 			std::cout << "comparisons: " << tracer<int>::count << ' ';
  180. 			std::cout << "inplace_sort took " << inplacesort_time << "s.\n";
  181. 		}
  182.         return 0;
  183. }
  184.  
  185.  
Success #stdin #stdout 4.12s 2840KB
comments (?)
stdin
copy 
40000
400000
4000000
stdout
copy 
comparisons: 823583 std::sort    took 0s.
comparisons: 1555789 quicksort    took 0s.
comparisons: 1255604 inplace_sort took 0s.
comparisons: 11147726 std::sort    took 0.03s.
comparisons: 18744579 quicksort    took 0.05s.
comparisons: 14920478 inplace_sort took 0.05s.
comparisons: 132047976 std::sort    took 0.41s.
comparisons: 225742099 quicksort    took 0.65s.
comparisons: 179079904 inplace_sort took 0.61s.
https://ideone.com/4iCSo
language:
C++14 (gcc 8.3)
created:
13 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!