This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Mergesort

By: cire3791 on Sep 29th, 2012  |  syntax: C++  |  size: 8.49 KB  |  views: 59  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #ifndef RANGE_H_EMS
  2. #define RANGE_H_EMS
  3.  
  4. #include <vector>
  5.  
  6. namespace MergeSort_EMS
  7. {
  8.     template <typename T>
  9.     class Range
  10.     {
  11.     public:
  12.         Range( T* begin, unsigned elements ) : _array(begin), _nElements(elements)
  13.         {
  14.         }
  15.  
  16.         unsigned size() const { return _nElements ; }
  17.         operator T*() { return _array; }
  18.  
  19.     private:
  20.  
  21.         T* _array ;
  22.         unsigned _nElements ;
  23.     };
  24.  
  25.  
  26.     // ranges fed to merge are expected to be contiguous memory where
  27.     // a would house the earlier of the indexes in an array that composed
  28.     // the two.
  29.     template <typename T>
  30.     Range<T> merge( Range<T> a, Range<T> b, std::vector<T>& scratch )
  31.     {
  32.         scratch.clear() ;
  33.  
  34.         Range<T> merged( a, a.size()+b.size() ) ;
  35.  
  36.         unsigned aIdx = 0 ;
  37.         unsigned bIdx = 0 ;
  38.         unsigned processed = 0 ;
  39.  
  40.         // members of a that are not greater than b[0] will not need to be moved.
  41.         while ( aIdx < a.size() && a[aIdx] <= b[bIdx] )
  42.             ++aIdx, ++processed ;
  43.  
  44.         // once we reach an element in a that is greater than b[0], the rest
  45.         // of the elements in a must be moved to scratch.
  46.         if ( aIdx < a.size() )
  47.         {
  48.             scratch.insert(scratch.begin(), a+aIdx, a+a.size() ) ;
  49.             unsigned sIdx = 0 ;
  50.  
  51.             while ( processed < merged.size() && sIdx < scratch.size() && bIdx < b.size() )
  52.             {
  53.                 if ( scratch[sIdx] <= b[bIdx] )
  54.                     merged[processed] = scratch[sIdx++] ;
  55.                 else
  56.                     merged[processed] = b[bIdx++] ;
  57.                 ++processed ;
  58.             }
  59.  
  60.             if ( processed == merged.size() )
  61.                 return merged ;
  62.  
  63.             if ( bIdx == b.size() )
  64.             {  // only stuff in scratch left
  65.                 while ( processed < merged.size() )
  66.                     merged[processed++] = scratch[sIdx++] ;
  67.             }
  68.         }
  69.  
  70.         // at this point, anything left in b should already be in the correct position.
  71.         return merged ;
  72.     }
  73. }
  74. #endif
  75.  
  76. #ifndef MERGESORT_H_EMS
  77. #define MERGESORT_H_EMS
  78.  
  79. #include <algorithm>
  80. #include <vector>
  81.  
  82.  
  83. namespace MergeSort_EMS
  84. {
  85.     template <typename T>
  86.     void twosies(T* array, unsigned size)
  87.     {
  88.         unsigned max_iterations = size / 2 ;
  89.  
  90.         for ( unsigned i=0; i < max_iterations; ++i )
  91.         {
  92.             if ( *array > *(array+1) )
  93.                 std::swap( *array, *(array+1) ) ;
  94.  
  95.             array += 2 ;
  96.         }
  97.     }
  98.  
  99.     template <typename T>
  100.     void merge_sort(std::vector<T> & sortee)
  101.     {
  102.         // prepare our two-element sorted subarrays
  103.         // reduces the maximum number of ranges we need to store
  104.         // at one time by half.
  105.         twosies(sortee.data(), sortee.size()) ;
  106.  
  107.         // memory buffer to feed to merge
  108.         std::vector<T> scratch ;
  109.         scratch.reserve((sortee.size()+1)/2) ;
  110.  
  111.         std::vector<Range<T>> ranges ;
  112.         ranges.reserve((sortee.size()+1)/2) ;
  113.  
  114.         // generate initial twosie Ranges
  115.         {
  116.             const unsigned num_twosies = sortee.size() / 2 ;
  117.             T* ptr = sortee.data() ;
  118.             for ( unsigned i=0;  i<num_twosies;  ++i )
  119.             {
  120.                 ranges.push_back(Range<T>(ptr, 2));
  121.                 ptr += 2;
  122.             }
  123.  
  124.             if ( sortee.size() % 2 )
  125.                 ranges.push_back(Range<T>(ptr, 1)) ;
  126.         }
  127.  
  128.         // work the merge
  129.         while ( ranges.size() > 1 )
  130.         {
  131.             unsigned max_to_merge = ranges.size() - ranges.size()%2 ;
  132.  
  133.             unsigned i ;
  134.             for ( i=0;  i<max_to_merge; i+=2 )
  135.             {
  136.                 Range<T> r1 = ranges[i] ;
  137.                 Range<T> r2 = ranges[i+1] ;
  138.  
  139.                 // CAUTION:  See merge definition/comments before changing what is fed to it.
  140.                 ranges[i/2] = merge(r1, r2, scratch) ;
  141.             }
  142.  
  143.             if ( ranges.size()%2 )    // odd man out
  144.                 ranges[i/2] = ranges.back() ;
  145.  
  146.             // Use of resize requires a default constructor if used with only one argument,
  147.             // Range doesn't have a default constructor and we don't need one.   Feed resize
  148.             // a bullshit argument so we don't have to implement a default constructor.  Since
  149.             // we're only reducing the size of the vector, it won't be used anyway.
  150.             ranges.resize(max_to_merge/2 + ranges.size()%2, Range<T>(0,0)) ;
  151.         }
  152.     }
  153. };
  154. #endif
  155.  
  156. #ifndef TOSORT_H_EMS
  157. #define TOSORT_H_EMS
  158.  
  159. #include <vector>
  160. #include <limits>
  161. #include <functional>
  162.  
  163. const unsigned nullindex = std::numeric_limits<unsigned>::max() ;
  164.  
  165. class ToSort
  166. {
  167. public:
  168.     static std::function<void(unsigned,unsigned, unsigned)> update_func ;
  169.  
  170.     ToSort(const std::vector<ToSort>& v, unsigned id) ;
  171.     ToSort(const ToSort & c);
  172.     ToSort(ToSort && c) ;
  173.  
  174.     ToSort& operator=(ToSort&&c) ;
  175.     ToSort& operator=(const ToSort& c) ;
  176.  
  177.     operator unsigned() const { return _id ; }
  178.  
  179. private:
  180.    
  181.     const std::vector<ToSort>* _container ;
  182.     unsigned _id ;
  183.     unsigned _prev_pos ;
  184.  
  185.  
  186.     void _update_notify() const ;
  187.     bool _in_container() const ;
  188.     unsigned _container_pos() const ;
  189. };
  190. #endif
  191.  
  192. #include <vector>
  193. #include <limits>
  194.  
  195.  std::function<void(unsigned,unsigned, unsigned)> ToSort::update_func = nullptr ;
  196.  
  197.  ToSort::ToSort(const std::vector<ToSort>& v, unsigned id)
  198.      : _container(&v), _id(id), _prev_pos(nullindex)
  199.  {
  200.  }
  201.  
  202.  ToSort::ToSort(const ToSort& c)
  203.      : _container(c._container), _id(c._id), _prev_pos(c._container_pos())
  204.  {
  205.     _update_notify() ;
  206.  }
  207.  
  208.  ToSort::ToSort(ToSort&& c)
  209.      : _container(c._container), _id(c._id), _prev_pos(c._container_pos())
  210.  {
  211.      _update_notify() ;
  212.  }
  213.  
  214.  ToSort& ToSort::operator=(ToSort&&c)
  215.  {
  216.      *this = c ;
  217.      c._container = nullptr ;
  218.      return *this ;
  219.  }
  220.  
  221.  ToSort& ToSort::operator=(const ToSort& c)
  222.  {
  223.      _container = c._container ;
  224.      _id = c._id ;
  225.      _prev_pos = c._container_pos() ;
  226.      _update_notify() ;
  227.      return *this ;
  228.  }
  229.  
  230.  void ToSort::_update_notify() const
  231.  {
  232.      if ( update_func != nullptr && _container != nullptr )
  233.          update_func(_container_pos(), _id, _prev_pos) ;
  234.  }
  235.  
  236.  // if we append or push a ToSort to the end of a container,
  237.  // _in_container() may be called before the container has updated
  238.  // its size to reflect the addition, so of this is one past the end
  239.  // of the container we will consider it to be in the container.
  240.  bool ToSort::_in_container() const
  241.  {
  242.      if ( _container == nullptr )
  243.          return false ;
  244.  
  245.     ToSort const * array = _container->data() ;
  246.  
  247.     if ( this >= array && array + _container->size() >= this )
  248.         return true ;
  249.  
  250.     return false ;
  251.  }
  252.  
  253. unsigned ToSort::_container_pos() const
  254. {
  255.     if ( _in_container() )
  256.         return this - _container->data() ;
  257.     else
  258.         return nullindex ;
  259. }
  260.  
  261. #include <numeric>
  262. #include <iostream>
  263. #include <vector>
  264. #include <random>
  265.  
  266. namespace ms = MergeSort_EMS ;
  267.  
  268. void populate_vector(std::vector<ToSort>& v)
  269. {
  270.     v.clear() ;
  271.  
  272.     std::random_device rd ;
  273.  
  274.     const unsigned v_size = rd() % 15 + 6 ;
  275.  
  276.     for ( unsigned i=0;  i<v_size;  ++i )
  277.         v.push_back(ToSort(v, i)) ;
  278.  
  279.     std::shuffle(v.begin(), v.end(), rd ) ;
  280. }
  281.  
  282. class OnUpdate
  283. {
  284.     std::vector<ToSort>& _v ;
  285. public:
  286.  
  287.     OnUpdate(std::vector<ToSort>& v) : _v(v) {}
  288.  
  289.     void operator()(unsigned index, unsigned id, unsigned prev_index)
  290.     {
  291.         if ( prev_index == nullindex )
  292.             std::cout << id << " was inserted  at " << index << '\n' ;
  293.         else
  294.         {
  295.             if ( index == nullindex )
  296.                 std::cout << id << " was removed from " << prev_index << '\n' ;
  297.             else
  298.                 std::cout << id << " was moved from " << prev_index << " to " << index << '\n' ;
  299.         }      
  300.     }
  301. };
  302.  
  303. void show(const std::vector<ToSort>& v)
  304. {
  305.     std::cout << "{ " ;
  306.     for ( unsigned i=0; i< v.size();  ++i )
  307.     {
  308.         std::cout << v[i] << ' ' ;
  309.     }
  310.     std::cout << "}\n" ;
  311. }
  312.  
  313. int main()
  314. {
  315.     std::vector<ToSort> v ;
  316.     v.reserve(100) ;
  317.     OnUpdate update(v) ;
  318.     ToSort::update_func = update ;
  319.        
  320.     do
  321.     {
  322.         ToSort::update_func = nullptr ;   // disable updating while populating the vector
  323.         populate_vector(v) ;
  324.         ToSort::update_func = update ;
  325.  
  326.         show(v) ;
  327.         ms::merge_sort(v) ;
  328.         show(v) ;
  329.  
  330.         std::cout << '\n' ;
  331.  
  332.     } while ( std::cin.get() == '\n' ) ;
  333. }
clone this paste RAW Paste Data