diff options
Diffstat (limited to 'include/EASTL/bonus/sort_extra.h')
| -rw-r--r-- | include/EASTL/bonus/sort_extra.h | 204 |
1 files changed, 204 insertions, 0 deletions
diff --git a/include/EASTL/bonus/sort_extra.h b/include/EASTL/bonus/sort_extra.h new file mode 100644 index 0000000..5f9a0c4 --- /dev/null +++ b/include/EASTL/bonus/sort_extra.h @@ -0,0 +1,204 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + +////////////////////////////////////////////////////////////////////////////// +// This file implements additional sort algorithms beyond the basic set. +// Included here are: +// selection_sort -- Unstable. +// shaker_sort -- Stable. +// bucket_sort -- Stable. +// +////////////////////////////////////////////////////////////////////////////// + + +#ifndef EASTL_SORT_EXTRA_H +#define EASTL_SORT_EXTRA_H + + +#include <EASTL/internal/config.h> +#include <EASTL/iterator.h> +#include <EASTL/algorithm.h> +#include <EASTL/functional.h> +#include <EASTL/heap.h> +#include <EASTL/sort.h> // For backwards compatibility due to sorts moved from here to sort.h. +#include <EASTL/allocator.h> + +#if defined(EA_PRAGMA_ONCE_SUPPORTED) + #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. +#endif + + + +namespace eastl +{ + /// selection_sort + /// + /// Implements the SelectionSort algorithm. + /// + template <typename ForwardIterator, typename StrictWeakOrdering> + void selection_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare) + { + ForwardIterator iCurrent, iMin; + + for(; first != last; ++first) + { + iCurrent = first; + iMin = iCurrent; + + for(++iCurrent; iCurrent != last; ++iCurrent) + { + if(compare(*iCurrent, *iMin)) + { + EASTL_VALIDATE_COMPARE(!compare(*iMin, *iCurrent)); // Validate that the compare function is sane. + iMin = iCurrent; + } + } + + if(first != iMin) + eastl::iter_swap(first, iMin); + } + } // selection_sort + + template <typename ForwardIterator> + inline void selection_sort(ForwardIterator first, ForwardIterator last) + { + typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less; + + eastl::selection_sort<ForwardIterator, Less>(first, last, Less()); + } + + + + /// shaker_sort + /// + /// Implements the ShakerSort algorithm, which is a sorting algorithm which + /// improves on bubble_sort by sweeping both from left to right and right + /// to left, resulting in less iteration. + /// + template <typename BidirectionalIterator, typename StrictWeakOrdering> + void shaker_sort(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering compare) + { + if(first != last) + { + BidirectionalIterator iCurrent, iNext, iLastModified; + + --last; + + while(first != last) + { + iLastModified = first; + + for(iCurrent = first; iCurrent != last; iCurrent = iNext) + { + iNext = iCurrent; + ++iNext; + + if(compare(*iNext, *iCurrent)) + { + EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane. + iLastModified = iCurrent; + eastl::iter_swap(iCurrent, iNext); + } + } + + last = iLastModified; + + if(first != last) + { + for(iCurrent = last; iCurrent != first; iCurrent = iNext) + { + iNext = iCurrent; + --iNext; + + if(compare(*iCurrent, *iNext)) + { + EASTL_VALIDATE_COMPARE(!compare(*iNext, *iCurrent)); // Validate that the compare function is sane. + iLastModified = iCurrent; + eastl::iter_swap(iNext, iCurrent); + } + } + first = iLastModified; + } + } + } + } // shaker_sort + + template <typename BidirectionalIterator> + inline void shaker_sort(BidirectionalIterator first, BidirectionalIterator last) + { + typedef eastl::less<typename eastl::iterator_traits<BidirectionalIterator>::value_type> Less; + + eastl::shaker_sort<BidirectionalIterator, Less>(first, last, Less()); + } + + + + /// bucket_sort + /// + /// Implements the BucketSort algorithm. + /// + /// Example usage: + /// const size_t kElementRange = 32; + /// vector<int> intArray(1000); + /// + /// for(int i = 0; i < 1000; i++) + /// intArray[i] = rand() % kElementRange; + /// + /// vector< vector<int> > bucketArray(kElementRange); + /// bucket_sort(intArray.begin(), intArray.end(), bucketArray, eastl::hash_use_self<int>()); + /// + template <typename T> + struct hash_use_self + { + T operator()(const T& x) const + { return x; } + }; + + // Requires buckeyArray to be an array of arrays with a size equal to the range of values + // returned by the hash function. The hash function is required to return a unique value + // for each uniquely sorted element. Usually the way this is done is the elements are + // integers of a limited range (e.g. 0-64) and the hash function returns the element value + // itself. If you had a case where all elements were always even numbers (e.g. 0-128), + // you could use a custom hash function that returns (element value / 2). + // + // The user is required to provide an empty bucketArray to this function. This function returns + // with the bucketArray non-empty. This function doesn't clear the bucketArray because that takes + // time and the user might not need it to be cleared, at least at that time. + // + template <typename ForwardIterator, typename ContainerArray, typename HashFunction> + void bucket_sort(ForwardIterator first, ForwardIterator last, ContainerArray& bucketArray, HashFunction hash /*= hash_use_self*/) + { + for(ForwardIterator iInput = first; iInput != last; ++iInput) + bucketArray[hash(*iInput)].push_back(*iInput); + + for(typename ContainerArray::const_iterator iBucket = bucketArray.begin(); iBucket != bucketArray.end(); ++iBucket) + first = eastl::copy((*iBucket).begin(), (*iBucket).end(), first); + } + + + +} // namespace eastl + + +#endif // Header include guard + + + + + + + + + + + + + + + + + + + + |