1 
  2 #include<vector>
  3 #include<stack>
  4 #include<algorithm>
  5 #include<iterator>
  6 #include<iostream>
  7 #include<math.h>
  8 
  9 namespace sorts
 10 {
 11     template<class RandomAccessIterator>
 12     bool is_sorted(RandomAccessIterator first, RandomAccessIterator last)
 13     {
 14         for(RandomAccessIterator it = first; it < last-1; ++it)
 15             if(*it > *(it+1))
 16                 return false;
 17         return true;
 18     }
 19 
 20     template<class RandomAccessIterator>
 21     void merge(RandomAccessIterator first, RandomAccessIterator last)
 22     {
 23         if( (last - first) > 2 )
 24         {
 25             RandomAccessIterator midpoint = first + (size_t)floor((double)(last - first)/2.0);
 26 
 27             //Recursive calls to sub ranges
 28             merge(first,midpoint);
 29             merge(midpoint,last);
 30 
 31             // Copy first part of the range, to avoid overwrite
 32             std::vector<typename RandomAccessIterator::value_type> tmp;
 33             tmp.reserve(midpoint-first);
 34             std::copy(first,midpoint,std::back_inserter(tmp));
 35 
 36             // Merge
 37             RandomAccessIterator it = tmp.begin(), jt = midpoint, kt = first;
 38             while( it < tmp.end() && jt < last )
 39             {
 40                 if( *it <= *jt)
 41                 {
 42                     *kt = *it;
 43                     ++it;
 44                 }
 45                 else
 46                 {
 47                     *kt = *jt;
 48                     ++jt;
 49                 }
 50                 ++kt;
 51             }
 52             for( ; it < tmp.end(); ++it, ++kt )
 53                 *kt = *it;
 54             for( ; jt < last; ++jt, ++kt )
 55                 *kt = *jt;
 56         }
 57         else if( (last - first) > 1 && *first > *(last-1) )
 58         {
 59             iter_swap( first, (last-1) );
 60         }
 61     }
 62 
 63     template<class RandomAccessIterator>
 64     void quick(RandomAccessIterator first, RandomAccessIterator last)
 65     {
 66         if(last > first)
 67         {
 68             RandomAccessIterator pivot = first;
 69             RandomAccessIterator lastelement = last - 1;
 70             for(RandomAccessIterator it = first; it < lastelement; ++it)
 71             {
 72                 if( *it < *lastelement )
 73                 {
 74                     iter_swap(pivot,it);
 75                     ++pivot;
 76                 }
 77             }
 78             iter_swap(pivot,lastelement);
 79 
 80             quick(first,pivot);
 81             quick(pivot+1,last);
 82         }
 83     }
 84 
 85     template<class RandomAccessIterator>
 86     void _heapify(RandomAccessIterator it, size_t root, size_t length)
 87     {
 88         size_t second_child = (root+1)*2;
 89         size_t first_child = second_child - 1;
 90         size_t big_child = length;
 91 
 92         if(second_child < length)
 93         {
 94             big_child = ( it[first_child] > it[second_child] ) ? first_child : second_child;
 95         }
 96         else if( first_child < length )
 97         {
 98             big_child = first_child;
 99         }
100 
101         if( big_child < length && it[big_child] > it[root] )
102         {
103             std::swap(it[big_child],it[root]);
104             _heapify(it,big_child,length);
105         }
106     }
107 
108     template<class RandomAccessIterator>
109     void _make_heap(RandomAccessIterator it, size_t root, size_t length)
110     {
111         size_t second_child = (root+1)*2;
112         size_t first_child = second_child - 1;
113 
114         if(first_child < length)
115             _make_heap(it,first_child,length);
116         if(second_child < length)
117             _make_heap(it,second_child,length);
118 
119         _heapify(it,root,length);
120     }
121 
122     template<class RandomAccessIterator>
123     void heap(RandomAccessIterator first, RandomAccessIterator last)
124     {
125         size_t length = last - first;
126         _make_heap(first, 0, length);
127 
128         for( --length; length > 0; --length )
129         {
130             std::swap(first[0], first[length]);
131             _heapify(first, 0, length);
132         }
133 
134     }
135 
136     template<class RandomAccessIterator>
137     void comb(RandomAccessIterator first, RandomAccessIterator last)
138     {
139         size_t gap = (last - first);
140         gap = (size_t)floor((double)gap / 1.247330950103979);
141 
142         while(gap > 1)
143         {
144             for( RandomAccessIterator jt = first, kt = first + gap; kt < last; ++jt, ++kt)
145                 if((*jt)>(*kt))
146                     iter_swap(jt,kt);
147 
148             gap = (size_t)floor((double)gap / 1.247330950103979);
149         }
150         smart_bubble(first, last);
151     }
152 
153     template<class RandomAccessIterator>
154     void bubble(RandomAccessIterator first, RandomAccessIterator last)
155     {
156         for( RandomAccessIterator it = last; it > first; --it )
157             for( RandomAccessIterator jt = first, kt = first + 1; kt < it; ++jt, ++kt)
158                 if((*jt)>(*kt))
159                     iter_swap(jt,kt);
160     }
161 
162     template<class RandomAccessIterator>
163     void smart_bubble(RandomAccessIterator first, RandomAccessIterator last)
164     {
165         bool swaped = true;
166         for( RandomAccessIterator it = last; it > first && swaped; --it )
167         {
168             swaped = false;
169             for( RandomAccessIterator jt = first, kt = first + 1; kt < it; ++jt, ++kt)
170                 if((*jt)>(*kt))
171                 {
172                     iter_swap(jt,kt);
173                     swaped = true;
174                 }
175         }
176     }
177 
178     template<class RandomAccessIterator>
179     void selection(RandomAccessIterator first, RandomAccessIterator last)
180     {
181         for( RandomAccessIterator it = first; it < last; ++it)
182         {
183             RandomAccessIterator min = it;
184             for( RandomAccessIterator jt = it + 1; jt < last; ++jt)
185                 if(*jt < *min) min = jt;
186             iter_swap(it,min);
187         }
188     }
189 
190     template<class RandomAccessIterator>
191     void insertion(RandomAccessIterator first, RandomAccessIterator last)
192     {
193         for( RandomAccessIterator it = first; it < last; ++it)
194         {
195             for( RandomAccessIterator current = it; current > first && *current < *(current-1); --current )
196                 iter_swap(current,current-1);
197         }
198     }
199 
200     //
201     // Patience sort implementation taken from wikipedia:
202     //
203     template<typename PileType>
204     bool pile_less(const PileType& x, const PileType& y)
205     {
206         return x.top() < y.top();
207     }
208 
209     // reverse less predicate to turn max-heap into min-heap
210     template<typename PileType>
211     bool pile_more(const PileType& x, const PileType& y)
212     {
213         return pile_less(y, x);
214     }
215 
216     template<typename RandomAccessIterator>
217     void patience(RandomAccessIterator begin, RandomAccessIterator end)
218     {
219         typedef typename std::iterator_traits<RandomAccessIterator>::value_type DataType;
220         typedef std::stack<DataType> PileType;
221         std::vector<PileType> piles;
222 
223         for (RandomAccessIterator it = begin; it != end; it++)
224         {
225             PileType new_pile;
226             new_pile.push(*it);
227             typename std::vector<PileType>::iterator insert_it =
228                 std::lower_bound(piles.begin(), piles.end(), new_pile,
229                                  pile_less<PileType>);
230             if (insert_it == piles.end())
231                 piles.push_back(new_pile);
232             else
233                 insert_it->push(*it);
234         }
235         // sorted array already satisfies heap property for min-heap
236 
237         for (RandomAccessIterator it = begin; it != end; it++)
238         {
239             std::pop_heap(piles.begin(), piles.end(), pile_more<PileType>);
240             *it = piles.back().top();
241             piles.back().pop();
242             if (piles.back().empty())
243                 piles.pop_back();
244             else
245                 std::push_heap(piles.begin(), piles.end(), pile_more<PileType>);
246         }
247     }
248 }