template <typename T>
size_t
partition(T a[], size_t left, size_t right) {
assert(left < right);
T pivot = a[left];
size_t l = left + 1;
// a[l .. l - 1] ≤ pivot < a[right .. right' - 1]
while (l < right)
if (a[l] ≤ pivot) l++;
else if (pivot < a[right - 1]) right--;
else std::swap(a[l++], a[--right]);
std::swap(a[left], a[--l]);
return l;
}
This page last modified on 24 January 2006.