The goal of the partition function is this: given a predicate function, put every element for which the predicate returns true
sequentially before every element for which the predicate returns false
The predicate function works by comparing each element to a pivot
(Your predicate is expressed as a function call:
compare( element, pivotValue )
So, let's assume for our purposes here that the predicate is true for any (x < pivot_value). Given a list like:
2 6 4 1 3
We'll choose the middle element (index 2, value 4) as the pivot. Our partition function should then move every element < 4 to the left, and every element not < 4 to the right:
2 1 3 4 6
Notice how the pivot's position (or index) moved? That happens.
Okay, not to work through your function:
template <class T>
vector<T>& set, // a horrible name, really
int start, // the index of the first sequential element to partition, inclusive
int end, // the index of the last sequential element to partition, inclusive
bool (*compare)(const T&, const T&)) // function used to implement our predicate
int pivotIndex, mid; // indices: where the new pivot index currently will be, and where we'll get our pivot from
T pivotValue; // a value: the value of our pivot
mid = (start + end) / 2; // We'll choose the middle element as our pivot*
// For the sorting, we'll move the element selected as our pivot to the
// very first element of our sub-array. That way we can conveniently
// exclude it from our partitioning. To make the move quick and painless,
// we'll just swap the two element values.
T temp = set[start];
set[start] = set[mid];
set[mid] = temp;
pivotIndex = start; // Our initial pivot index is where we just moved the pivot value to.
pivotValue = set[start]; // The pivot value, for convenient use. This will not change.
// Now we'll loop through all the elements in the remaining spaces (not the pivot)
for (int scan = start + 1; scan <= end; scan++)
if (compare(set[scan], pivotValue)) // our predicate: element ?? pivotValue
// okay, we got in here because this element is to be moved before the final pivot position
// so we'll bump our final pivot index up by one (so that now it indexes
// the first element after the final pivot position)
//pivotIndex and scan of the vector // what? this comment does not help us understand the algorithm.
// (scan --> element that goes before pivot, pivotIndex --> element that goes after)
// swap them, so
// (pivotIndex --> element that goes before pivot, scan --> element that goes after)
T newTemp = set[pivotIndex];
set[pivotIndex] = set[scan];
set[scan] = newTemp;
// Good so far. Now we have everything positioned -- except the actual
// pivot value is still sitting at the beginning of our sub-array. We need to
// move it back to the new pivot index. Simple enough: we'll just swap
// again. (Remember, the thing under pivotIndex --> element that goes
// before pivot, so swapping will make that true for every 'before' element we found.)
T thirdTemp = set[start];
set[start] = set[pivotIndex];
set[pivotIndex] = thirdTemp;
// Now pivotIndex really does point to the pivot value.
* To avoid overflow problems, it should be calculated as
mid = start + (end - start + 1) / 2;
. Don't forget that off-by-one there.
Notice that the actual order
of elements before and after the pivot don't matter.
More reading on quicksort:
Hope this helps.