# Iterator based version of quicksort, allowing user defined pivot-selection-strategy

I have implemented a iterator based version of Quicksort, which allows the user to define and pass his own pivot-selection-strategy:

template<typename It>
It Partition(It begin,It end,It pivot)
{
std::swap(*begin, *pivot);
pivot = begin;
It i{ begin }, j = std::next(begin, 1);
for(;j != end; j++)
{
if(*j < *pivot)
std::swap(*j, *++i);
}
std::swap(*pivot, *i);
return i;
}

template<typename It, typename Pivot>
void Quicksort(It begin, It end, Pivot&& GetPivot)
{
if (std::distance(begin, end) == 0)
return;
It pivot{ GetPivot(begin,end) };
It elementAtCorrectPosition = Partition(begin, end,pivot);
Quicksort(begin, elementAtCorrectPosition, GetPivot);
Quicksort(std::next(elementAtCorrectPosition, 1), end, GetPivot);
}


The algorithm can be used in the following way:

std::vector<int> v{  3, 8, 2, 5, 1, 4, 7, 6 };
auto quickSort = v;
auto stdSort = v;
Quicksort(quickSort.begin(),
quickSort.end(),
[](auto a, auto b) { return a; });
std::sort(stdSort.begin(), stdSort.end());
Assert::IsTrue(quickSort == stdSort);


Where the lambda expression

 [](auto a, auto b) { return a; }


is just to demonstrate how a pivot selection strategy can be passed to the algorithm.

Any suggestions that lead to a more robust, concise and readable code are welcome.

Special thanks to @ratchet freak, who discovered an emberassing bug:

The initial implementation only worked for the special case, where the first element is selected as pivot. See above for the corrected version.

• I'm pretty sure you need to swap(*begin, *pivot); pivot = begin; at the start of partition. Otherwise the pivot could move. Commented Mar 17, 2017 at 12:14
• Why are you not using std::partition? Commented Mar 17, 2017 at 12:20
• "Why are you not using std::partition" For practicing purposes... Commented Mar 17, 2017 at 12:21
• @ratchetfreak: You are absolutely right . my initial version only worked for the special case, where the first element is selected as pivot. Thats what happens, if tests are not randomized :-) See the updated op, which includes the corrected version. Commented Mar 17, 2017 at 16:22

One thing that is missing is selecting a custom comparison function. This is usually done by adding a std::less like type to the template and passing that on to the partition

template<typename It, typename Compare>
It Partition(It begin,It end,It pivot, Compare comp)
{
std::swap(*begin, *pivot);
pivot = begin;
It i{ begin }, j = std::next(begin, 1);
for(;j != end; j++)
{
if(comp(*j, *pivot))
std::swap(*j, *++i);
}
std::swap(*pivot, *i);
return i;
}

• Wouldn't Compare deserve a default like std::less also then? Commented Mar 17, 2017 at 12:23
• @πάνταῥεῖ, not in partition as it's an internal util function, but for the sort you could make it a default or add an overload. Commented Mar 17, 2017 at 12:28
• Sure, that was what I meant. Didn't spot that clearly. Commented Mar 17, 2017 at 13:02