SHARE
TWEET

MergeSort3

Argentum_02 Nov 12th, 2019 (edited) 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "test_runner.h"
  2. #include <algorithm>
  3. #include <memory>
  4. #include <vector>
  5. #include <typeinfo>
  6. #include <cstdint>
  7. #include <list>
  8. #include "iostream"
  9. #include <utility>
  10.  
  11. using namespace std;
  12.  
  13. void print(string message,vector<int> &numbers){
  14.     cout << message << endl;
  15.     for(auto &it:numbers){
  16.         cout << it << ",";
  17.     }
  18.     cout << endl;
  19. }
  20.  
  21. // ::working code::
  22. template <typename RandomIt>
  23. void MergeSort(RandomIt range_begin, RandomIt range_end) {
  24.     if(range_end - range_begin <3){
  25.         return;
  26.     }
  27.     vector<typename RandomIt::value_type> elements(move(range_begin),move(range_end));
  28.     vector<typename RandomIt::value_type> space,space2,space3,res;
  29.     move(elements.begin(),elements.begin()+(elements.end() - elements.begin())/3,back_inserter(space));
  30.     move(elements.begin()+(elements.end() - elements.begin())/3,elements.begin()+(elements.end() - elements.begin())/3*2,back_inserter(space2));
  31.     MergeSort(space.begin(),space.end());
  32.     MergeSort(space2.begin(),space2.end());
  33.     MergeSort(elements.begin()+(elements.end() - elements.begin())/3*2,elements.end());
  34.     merge(make_move_iterator(space.begin()),make_move_iterator(space.end()),make_move_iterator(space2.begin()),make_move_iterator(space2.end()),back_inserter(res));
  35.     merge(make_move_iterator(res.begin()),make_move_iterator(res.end()),make_move_iterator(elements.begin()+(elements.end() - elements.begin())/3*2),make_move_iterator(elements.end()),back_inserter(space3));
  36.     move(make_move_iterator(space3.begin()),make_move_iterator(space3.end()),range_begin);
  37. //      for(size_t i=0;i<space3.size();i++,++range_begin){
  38. //      *range_begin = move(space3[i]);
  39. //  }
  40. }
  41.  
  42.  
  43. void TestIntVector() {
  44.   vector<int> numbers = {6, 1, 3, 9, 1, 9, 8, 12, 1};
  45.   MergeSort(begin(numbers), end(numbers));
  46.   ASSERT(is_sorted(begin(numbers), end(numbers)));
  47. }
  48.  
  49.  
  50.  
  51. int main() {
  52.   TestRunner tr;
  53.   RUN_TEST(tr, TestIntVector);
  54.   return 0;
  55. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top