3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm pretty sure you need to swap(*begin, *pivot); pivot = begin; at the start of partition. Otherwise the pivot could move. \$\endgroup\$ – ratchet freak Mar 17 '17 at 12:14
  • 1
    \$\begingroup\$ Why are you not using std::partition? \$\endgroup\$ – Emily L. Mar 17 '17 at 12:20
  • \$\begingroup\$ "Why are you not using std::partition" For practicing purposes... \$\endgroup\$ – user1934212 Mar 17 '17 at 12:21
  • \$\begingroup\$ @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. \$\endgroup\$ – user1934212 Mar 17 '17 at 16:22
2
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Wouldn't Compare deserve a default like std::less also then? \$\endgroup\$ – πάντα ῥεῖ Mar 17 '17 at 12:23
  • 1
    \$\begingroup\$ @πάνταῥεῖ, not in partition as it's an internal util function, but for the sort you could make it a default or add an overload. \$\endgroup\$ – ratchet freak Mar 17 '17 at 12:28
  • \$\begingroup\$ Sure, that was what I meant. Didn't spot that clearly. \$\endgroup\$ – πάντα ῥεῖ Mar 17 '17 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.