Template Function ADS::partitionByValue

• Defined in File QuickSort.h

Function Documentation

template<class T, class C = std::less<>>
std::size_t ADS::partitionByValue(std::vector<T> &A, std::size_t start, std::size_t end, const T &x, C less = C())

the partition of A[ start .

. end ] around a value x that need not be in it: the items not larger than x first, the larger ones after, in one pass from both ends; the number of the items not larger than x

Pre:

start <= end < n

Post:

A[ start .. start + r ) <= x < A[ start + r .. end ], the same items (an audit)