diff options
Diffstat (limited to 'src/include/util')
-rw-r--r-- | src/include/util/impl/qsort.H | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/src/include/util/impl/qsort.H b/src/include/util/impl/qsort.H new file mode 100644 index 000000000..3146d7d73 --- /dev/null +++ b/src/include/util/impl/qsort.H @@ -0,0 +1,189 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/util/impl/qsort.H $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_IMPL_QSORT_H +#define __UTIL_IMPL_QSORT_H + +/** @file qsort.H + * + * Contains the internal implementation details of std::sort implemented as + * quick-sort. + */ + +#include <iterator> + +// Forward declaration due to 'swap' being defined in <algorithm> which is +// including this file itself. +namespace std +{ + template <typename T> void swap(T& a, T& b); +}; + +namespace Util +{ + namespace __Util_QSort_Impl + { + template <typename RandomAccessIterator> + void sort(RandomAccessIterator first, RandomAccessIterator last) + { + size_t length = std::distance(first, last); + + // A range of length 0 or 1 is already sort. + if ((length == 0) || (length == 1)) + { + return; + } + + // A range of length 2 has a trivial sort. + if (length == 2) + { + RandomAccessIterator next = first; + std::advance(next, 1); + + if (*next < *first) + { + std::swap(*first, *next); + } + return; + } + + // Choose pivot as middle and move pivot to end. + // This is done to eliminate the O(n^2) behavior when the + // range is already sorted. + RandomAccessIterator pivot = first; + std::advance(pivot,length - 1); + RandomAccessIterator middle = first; + std::advance(middle, length / 2); + std::swap(*pivot, *middle); + + // Perform partitioning... + + // Division points to the first element greater than the pivot or + // else the farthest point partitioned if no elements greater than + // the pivot have been found yet. + RandomAccessIterator division = first; + RandomAccessIterator pos = first; + while(pos != pivot) + { + // Element less than the pivot is found, so move it to the + // "less than" side of the division line. + if (*pos < *pivot) + { + if (pos != division) + { + std::swap(*pos, *division); + } + ++division; + } + + ++pos; + } + + // Move the pivot down to the division line, which is its sorted + // position in the range. + if (pivot != division) + { + std::swap(*pivot,*division); + } + + // Sort each partition. + sort(first,division); + std::advance(division, 1); + sort(division, last); + }; + + + template <typename RandomAccessIterator, typename StrictWeakOrdering> + void sort(RandomAccessIterator first, RandomAccessIterator last, + StrictWeakOrdering pred) + { + size_t length = std::distance(first, last); + + // A range of length 0 or 1 is already sort. + if ((length == 0) || (length == 1)) + { + return; + } + + // A range of length 2 has a trivial sort. + if (length == 2) + { + RandomAccessIterator next = first; + std::advance(next, 1); + + if (pred(*next,*first)) + { + std::swap(*first, *next); + } + return; + } + + // Choose pivot as middle and move pivot to end. + // This is done to eliminate the O(n^2) behavior when the + // range is already sorted. + RandomAccessIterator pivot = first; + std::advance(pivot,length - 1); + RandomAccessIterator middle = first; + std::advance(middle, length / 2); + std::swap(*pivot, *middle); + + // Perform partitioning... + + // Division points to the first element greater than the pivot or + // else the farthest point partitioned if no elements greater than + // the pivot have been found yet. + RandomAccessIterator division = first; + RandomAccessIterator pos = first; + while(pos != pivot) + { + // Element less than the pivot is found, so move it to the + // "less than" side of the division line. + if (pred(*pos,*pivot)) + { + if (pos != division) + { + std::swap(*pos, *division); + } + ++division; + } + + ++pos; + } + + // Move the pivot down to the division line, which is its sorted + // position in the range. + if (pivot != division) + { + std::swap(*pivot,*division); + } + + // Sort each partition. + sort(first,division); + std::advance(division, 1); + sort(division, last); + }; + + }; +}; + +#endif |