HiveBrain v1.2.0
Get Started
← Back to all entries
snippetcppMinor

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

Submitted by: @import:stackexchange-codereview··
0
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:

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 partition

template
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.