fork download 
  1. #include <algorithm>
  2. #include <functional>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <cassert>
  6.  
  7. //This sort needs to work on a series of "chunks" in a certain format.
  8. // Each chunk is: 1 pivot followed by data < this pivot, but >= previous pivot
  9. //     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
  10. //     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]
  11. // 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]
  12. //    splitting each chunk into two subchunks: [16,7,8,6,6,12,14,13,8,6,5,15,6,12,0,10],[17,16,]
  13. // A chunk that is 1 element (only the pivot, no other data) is in the correct location.
  14. template<class bidi_iterator, class predicate>
  15. void inplace_sort(const bidi_iterator first, const bidi_iterator last, const predicate& pred) {
  16. 	using std::swap;
  17. 	if (first == last)
  18. 		return;
  19. 	bidi_iterator left = first;
  20. 	//Rearrange the origional data into "Chunks"
  21. 	while(left != last) {
  22. 		bidi_iterator mid = std::partition(left+1, last, std::bind2nd(pred, *left));
  23. 		left = mid;
  24. 	}
  25. 	bool again; //while there might still be unsorted data
  26. 	do {
  27. 		left = first; //iterate over data
  28. 		again = false;
  29. 		do { //iterate over each chunk
  30. 			bidi_iterator next = std::next(left);
  31. 			if (next == last) 
  32. 				break;
  33. 			//skip chunks that are only the pivot.
  34. 			//IE, find two elements out of order
  35. 			while(std::next(next) != last && pred(*left, *next)) {
  36. 				++left;
  37. 				++next;
  38. 			}
  39. 			//find the end of the chunk
  40. 			//IE next element bigger than pivot
  41. 			bidi_iterator right = std::next(next);
  42. 			int len=2;
  43. 			while(right!=last && pred(*right, *left)) {
  44. 				++len;
  45. 				++right;
  46. 			}
  47. 			bidi_iterator mid = right; //arbitrary assignment
  48. 			// if it's two, just swap
  49. 			if (len == 2)
  50. 				swap(*next, *left);	
  51. 			else { 
  52. 				//if more than two, partition into two seperate chunks
  53. 				//first, select a new pivot (next) and partition
  54. 				mid = std::partition(std::next(next), right, std::bind2nd(pred, *next));	
  55. 				//this means we have to move the pivots
  56. 				//the new(next) pivot begins the first chunk
  57. 				//the old(left) pivot begins the second chunk
  58. 				swap(*left, *next);
  59. 				bidi_iterator prev = std::prev(mid);
  60. 				if (next != prev)
  61. 					swap(*next, *prev);
  62. 				//There might be more data, do another pass
  63. 				again = true;
  64. 			}
  65. 			//move to the next chunk
  66. 			left = right;
  67. 		} while(left!=last); //continue until we do all the chunks in the data
  68. 	} while(again); //continue until we're sorted
  69. 	assert(std::is_sorted(first, last));
  70. 	return;
  71. }
  72.  
  73. template<class bidi_iterator>
  74. void inplace_sort(bidi_iterator begin, bidi_iterator end) {
  75. 	typedef typename std::iterator_traits<bidi_iterator>::value_type value_type;
  76. 	return inplace_sort(begin, end, std::less<value_type>());
  77. }
  78.  
  79. #include <cstdlib>
  80. #include <ctime>
  81. #include <vector>
  82.  
  83. template <typename T>
  84. struct tracer : std::less<T> {
  85.     static int count;
  86.  
  87.     bool operator()(T x, T y) const {
  88.         ++count;
  89.         return std::less<T>::operator()(x, y);
  90.     }
  91. };
  92. template <typename T>
  93. int tracer<T>::count = 0;
  94.  
  95. int main() {
  96.         unsigned test_size;
  97.         std::cin >> test_size;
  98.  
  99. 	double stdsort_time=0;
  100. 	double inplacesort_time=0;
  101. 	srand((unsigned)time(NULL));
  102. 	std::vector<int> data(test_size);
  103. 	for(unsigned i=0; i<data.size(); ++i)
  104. 		data[i] = 10000+rand();
  105. 	std::vector<int> data2;
  106. 	{
  107. 		data2 = data;
  108. 		std::sort(data2.begin(), data2.end(), tracer<int>());
  109. 		data2 = data;
  110. 		clock_t begin = clock();
  111. 		std::sort(data2.begin(), data2.end());
  112. 		clock_t end = clock();
  113. 		stdsort_time = double(end-begin)/CLOCKS_PER_SEC;
  114. 	}
  115.         std::cout << "comparisons: " << tracer<int>::count << '\n';
  116.         tracer<int>::count = 0;
  117. 	std::cout << "std::sort    took " << stdsort_time << "s.\n";
  118. 	{
  119. 		data2 = data;
  120. 		inplace_sort(data2.begin(), data2.end(), tracer<int>());
  121. 		data2 = data;
  122. 		clock_t begin = clock();
  123. 		inplace_sort(data2.begin(), data2.end());
  124. 		clock_t end = clock();
  125. 		inplacesort_time = double(end-begin)/CLOCKS_PER_SEC;
  126. 	}
  127.         std::cout << "comparisons: " << tracer<int>::count << '\n';
  128. 	std::cout << "inplace_sort took " << inplacesort_time << "s.\n";
  129. 	return 0;
  130. }
  131.  
Runtime error #stdin #stdout 0.52s 10792KB
comments (?)
stdin 
1000000
stdout 
comparisons: 26417984
std::sort    took 0.09s.
https://ideone.com/6trDX
language:
C++14 (gcc 8.3)
created:
13 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!