snippetcppMinor
Iterator based version of quicksort, allowing user defined pivot-selection-strategy
Viewed 0 times
allowingselectioniteratorversionuserpivotquicksortbasedstrategydefined
Problem
I have implemented a iterator based version of Quicksort, which allows the user to define and pass his own pivot-selection-strategy:
The algorithm can be used in the following way:
Where the lambda expression
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.
template
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
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 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.
Solution
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 partitiontemplate
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;
}Code Snippets
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;
}Context
StackExchange Code Review Q#158018, answer score: 2
Revisions (0)
No revisions yet.