1 ///////////////////////////////////////////////////////////////////////////// 2 // Copyright (c) Electronic Arts Inc. All rights reserved. 3 ///////////////////////////////////////////////////////////////////////////// 4 5 ////////////////////////////////////////////////////////////////////////////// 6 // This file implements additional sort algorithms beyond the basic set. 7 // Included here are: 8 // selection_sort -- Unstable. 9 // shaker_sort -- Stable. 10 // bucket_sort -- Stable. 11 // 12 ////////////////////////////////////////////////////////////////////////////// 13 14 15 #ifndef EASTL_SORT_EXTRA_H 16 #define EASTL_SORT_EXTRA_H 17 18 19 #include <EASTL/internal/config.h> 20 #include <EASTL/iterator.h> 21 #include <EASTL/algorithm.h> 22 #include <EASTL/functional.h> 23 #include <EASTL/heap.h> 24 #include <EASTL/sort.h> // For backwards compatibility due to sorts moved from here to sort.h. 25 #include <EASTL/allocator.h> 26 27 #if defined(EA_PRAGMA_ONCE_SUPPORTED) 28 #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result. 29 #endif 30 31 32 33 namespace eastl 34 { 35 /// selection_sort 36 /// 37 /// Implements the SelectionSort algorithm. 38 /// 39 template <typename ForwardIterator, typename StrictWeakOrdering> selection_sort(ForwardIterator first,ForwardIterator last,StrictWeakOrdering compare)40 void selection_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare) 41 { 42 ForwardIterator iCurrent, iMin; 43 44 for(; first != last; ++first) 45 { 46 iCurrent = first; 47 iMin = iCurrent; 48 49 for(++iCurrent; iCurrent != last; ++iCurrent) 50 { 51 if(compare(*iCurrent, *iMin)) 52 { 53 EASTL_VALIDATE_COMPARE(!compare(*iMin, *iCurrent)); // Validate that the compare function is sane. 54 iMin = iCurrent; 55 } 56 } 57 58 if(first != iMin) 59 eastl::iter_swap(first, iMin); 60 } 61 } // selection_sort 62 63 template <typename ForwardIterator> selection_sort(ForwardIterator first,ForwardIterator last)64 inline void selection_sort(ForwardIterator first, ForwardIterator last) 65 { 66 typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less; 67 68 eastl::selection_sort<ForwardIterator, Less>(first, last, Less()); 69 } 70 71 72 73 /// shaker_sort 74 /// 75 /// Implements the ShakerSort algorithm, which is a sorting algorithm which 76 /// improves on bubble_sort by sweeping both from left to right and right 77 /// to left, resulting in less iteration. 78 /// 79 template <typename BidirectionalIterator, typename StrictWeakOrdering> shaker_sort(BidirectionalIterator first,BidirectionalIterator last,StrictWeakOrdering compare)80 void shaker_sort(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering compare) 81 { 82 if(first != last) 83 { 84 BidirectionalIterator iCurrent, iNext, iLastModified; 85 86 --last; 87 88 while(first != last) 89 { 90 iLastModified = first; 91 92 for(iCurrent = first; iCurrent != last; iCurrent = iNext) 93 { 94 iNext = iCurrent; 95 ++iNext; 96 97 if(compare(*iNext, *iCurrent)) 98 { 99 EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane. 100 iLastModified = iCurrent; 101 eastl::iter_swap(iCurrent, iNext); 102 } 103 } 104 105 last = iLastModified; 106 107 if(first != last) 108 { 109 for(iCurrent = last; iCurrent != first; iCurrent = iNext) 110 { 111 iNext = iCurrent; 112 --iNext; 113 114 if(compare(*iCurrent, *iNext)) 115 { 116 EASTL_VALIDATE_COMPARE(!compare(*iNext, *iCurrent)); // Validate that the compare function is sane. 117 iLastModified = iCurrent; 118 eastl::iter_swap(iNext, iCurrent); 119 } 120 } 121 first = iLastModified; 122 } 123 } 124 } 125 } // shaker_sort 126 127 template <typename BidirectionalIterator> shaker_sort(BidirectionalIterator first,BidirectionalIterator last)128 inline void shaker_sort(BidirectionalIterator first, BidirectionalIterator last) 129 { 130 typedef eastl::less<typename eastl::iterator_traits<BidirectionalIterator>::value_type> Less; 131 132 eastl::shaker_sort<BidirectionalIterator, Less>(first, last, Less()); 133 } 134 135 136 137 /// bucket_sort 138 /// 139 /// Implements the BucketSort algorithm. 140 /// 141 /// Example usage: 142 /// const size_t kElementRange = 32; 143 /// vector<int> intArray(1000); 144 /// 145 /// for(int i = 0; i < 1000; i++) 146 /// intArray[i] = rand() % kElementRange; 147 /// 148 /// vector< vector<int> > bucketArray(kElementRange); 149 /// bucket_sort(intArray.begin(), intArray.end(), bucketArray, eastl::hash_use_self<int>()); 150 /// 151 template <typename T> 152 struct hash_use_self 153 { operatorhash_use_self154 T operator()(const T& x) const 155 { return x; } 156 }; 157 158 // Requires buckeyArray to be an array of arrays with a size equal to the range of values 159 // returned by the hash function. The hash function is required to return a unique value 160 // for each uniquely sorted element. Usually the way this is done is the elements are 161 // integers of a limited range (e.g. 0-64) and the hash function returns the element value 162 // itself. If you had a case where all elements were always even numbers (e.g. 0-128), 163 // you could use a custom hash function that returns (element value / 2). 164 // 165 // The user is required to provide an empty bucketArray to this function. This function returns 166 // with the bucketArray non-empty. This function doesn't clear the bucketArray because that takes 167 // time and the user might not need it to be cleared, at least at that time. 168 // 169 template <typename ForwardIterator, typename ContainerArray, typename HashFunction> bucket_sort(ForwardIterator first,ForwardIterator last,ContainerArray & bucketArray,HashFunction hash)170 void bucket_sort(ForwardIterator first, ForwardIterator last, ContainerArray& bucketArray, HashFunction hash /*= hash_use_self*/) 171 { 172 for(ForwardIterator iInput = first; iInput != last; ++iInput) 173 bucketArray[hash(*iInput)].push_back(*iInput); 174 175 for(typename ContainerArray::const_iterator iBucket = bucketArray.begin(); iBucket != bucketArray.end(); ++iBucket) 176 first = eastl::copy((*iBucket).begin(), (*iBucket).end(), first); 177 } 178 179 180 181 } // namespace eastl 182 183 184 #endif // Header include guard 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205