10
\$\begingroup\$

Original

quicksort.h

#include <algorithm>

namespace quicksort {

template <typename iterator, typename value_type>
struct traits 
{
    static iterator choose_pivot (iterator first, iterator last) {
        return first + (last - first) / 2 ;
    }

    static iterator partition (iterator first, iterator last, iterator pivot) {
        --last ;
        traits::swap (*pivot, *last) ;
        pivot = last ;

        while (true) {
            while (*first < *pivot) {
                ++first ;
            }

            --last ;

            while (*pivot < *last) {
                --last ;
            }

            if (first >= last) {
                traits::swap (*pivot, *first) ;
                return first ;
            }

            traits::swap (*first, *last) ;
            ++first ;
        }
    }

    static void swap (value_type &lhs, value_type &rhs) {
        std::swap (lhs, rhs) ;
    }
};


template <typename iterator, typename value_type>
void sort (iterator first, iterator last)
{
    if (first >= last) {
        return ;
    }

    auto pivot = traits<iterator, value_type>::choose_pivot (first, last) ;
    auto next_pivot = traits<iterator, value_type>::partition (first, last, pivot) ;
    sort <iterator, value_type> (first, next_pivot) ;
    sort <iterator, value_type> (next_pivot + 1, last) ;
}

} // end of namespace quicksort

Driver.cpp

#include "quicksort.h"
#include <vector>
#include <string>
#include <iostream>

template <typename DataType, template <typename ...> class Container>
void print_container (const Container <DataType> &container)
{
    for (const DataType &d : container) {
        std::cout << d << " " ;
    }

    std::cout << std::endl ;
}

template <typename DataType, template <typename ...> class Container>
void run_test (const std::string &name, Container <DataType> &&container)
{
    std::cout << name << ":\n" ;
    print_container <DataType, Container> (container) ;
    quicksort::sort <typename Container<DataType>::iterator, DataType> (std::begin (container), std::end (container)) ;
    std::cout << name << " quicksorted:\n" ;
    print_container <DataType, Container> (container) ;
}

int main (void)
{
    run_test <int, std::vector> ("vec1", std::vector <int> {5, 4, 3, 1, 2}) ;
    run_test <int, std::vector> ("vec2", std::vector <int> {5, 4, 10, 7, 6, 11, 14, 17, 12, 3, 1, 2}) ;

    return 0 ;
}


Updated

quicksort.h

#include <algorithm>
#include <iterator>

namespace quicksort {
namespace detail {

struct first_pivot_selector
{
    template <typename Iterator>
    static Iterator choose_pivot (Iterator first, Iterator last) {
        return first ;
    }
};

struct middle_pivot_selector
{
    template <typename Iterator>
    static Iterator choose_pivot (Iterator first, Iterator last) {
        auto distance = std::distance (first, last) / 2 ;
        std::advance (first, distance) ;
        return first ;
    }
};

struct last_pivot_selector
{
    template <typename Iterator>
    static Iterator choose_pivot (Iterator first, Iterator last) {
        return last ;
    }
};

// Kept for debugging
struct my_pivot_selector
{
    template <typename Iterator>
    static Iterator choose_pivot (Iterator first, Iterator last) {
        return first + (last - first) / 2 ;
    }
};

struct std_partition {
    template <typename Iterator>
    static Iterator partition (Iterator first, Iterator last, Iterator pivot)
    {
        using value_type = typename std::iterator_traits<Iterator>::value_type ;
        return std::stable_partition (first, last, [=] (const value_type &v) {
            return v < *pivot ;
        }) ;
    }
};

// Kept for debugging
struct my_partition
{
    template <typename Iterator>
    static Iterator partition (Iterator first, Iterator last, Iterator pivot)
    {
        --last ;
        std::swap (*pivot, *last) ;
        pivot = last ;

        while (true) {
            while (*first < *pivot) {
                ++first ;
            }

            --last ;

            while (*pivot < *last) {
                --last ;
            }

            if (first >= last) {
                std::swap (*pivot, *first) ;
                return first ;
            }

            std::swap (*first, *last) ;
            ++first ;
        }
    }
};

} // end of namespace detail

template <typename Iterator, typename Pivot = detail::middle_pivot_selector, typename Partition = detail::my_partition>
void sort (Iterator first, Iterator last)
{
    if (first >= last) {
        return ;
    }

    auto pivot = Pivot::choose_pivot (first, last) ;
    auto next_pivot = Partition::partition (first, last, pivot) ; 
    sort <Iterator, Pivot, Partition> (first, next_pivot) ;
    sort <Iterator, Pivot, Partition> (next_pivot + 1, last) ;
}

} // end of namespace quicksort

Driver.cpp

#include "quicksort.h"
#include <vector>
#include <string>
#include <iostream>

template <typename Container>
void print_container (const Container &container)
{
    for (const typename Container::value_type &v : container) {
        std::cout << v << " " ;
    }

    std::cout << std::endl ;
}

template <typename Container>
void run_test (const std::string &name, Container container)
{
    std::cout << name << ":\n" ;
    print_container (container) ;
    quicksort::sort (std::begin (container), std::end (container)) ;
    std::cout << name << " quicksorted:\n" ;
    print_container (container) ;
}

int main (void)
{
    run_test ("vec1", std::vector <int> {5, 4, 3, 1, 2}) ;
    run_test ("vec2", std::vector <int> {5, 4, 10, 7, 6, 11, 14, 17, 12, 3, 1, 2}) ;

    return 0 ;
}


Problem
Based on these changes, std_partition::partition produces incorrect results. I found some code that follows a similar strategy on wikibooks.

T middle = partition (begin, end, bind2nd(
                    less<typename iterator_traits<T>::value_type>(), *begin));
sort (begin, middle);
T new_middle = begin;
sort (++new_middle, end);

The problem is that this would break my current algorithm. I guess I could do a partial-specialization.

\$\endgroup\$
  • \$\begingroup\$ I'm sorry that I asking this. But you trying to implement quicksort algoritm, or it is somehow different from std::sort? There is no offense, I just not really good understand quicksort algoritm, and can't figure out, is it better than std's one? \$\endgroup\$ – tower120 May 22 '14 at 16:18
8
\$\begingroup\$

Let's start with things that can be cleaned up in your traits struct:

Firstly, by convention, all template parameters should be UpperCaseFirstLetter. Secondly, you don't need to pass in a value_type, because you can get this directly from the iterator using std::iterator_traits. Finally, using a struct with all static functions smells a bit: this should simply be an inner namespace. Usually, when it's details that you don't want to expose to people, the chosen name for the namespace would be detail. Let's apply that to the choose_pivot function:

#include <iterator>

namespace quicksort
{
namespace detail
{

template <typename Iterator>
Iterator choose_pivot(Iterator first, Iterator last)
{
    auto distance = std::distance(first, last) / 2;
    std::advance(first, distance);
    return first;
}

} // end namespace detail

...

It's now using std::distance and std::advance. This will work with any iterator type, but performance will obviously be degraded. If you want to enforce that the iterator is random access, you can always throw in a static_assert:

 static_assert(std::is_same<std::iterator_traits<Iterator>::iterator_category,
                            std::random_access_iterator_tag>::value,
               "Iterator must be random access");

The partition function you've got currently could be very easily replaced with std::partition:

template <typename Iterator>
Iterator partition(Iterator first, Iterator last, Iterator pivot)
{
    using value_type = typename std::iterator_traits<Iterator>::value_type;
    return std::partition(first, last, [=](const value_type& v) { return v < *pivot; });
}

If you want to make it really customisable, then I'd suggest doing that as template parameters on the sort function. Also, it's always a good idea to provide defaults, because otherwise your users are going to have to specify masses of template parameters, which is annoying. This will require modifying the choose_pivot function above into a struct\class:

namespace detail
{
struct pivot
{
    template <typename Iterator>
    Iterator choose_pivot(Iterator first, Iterator last)
    {
        auto distance = std::distance(first, last) / 2;
        std::advance(first, distance);
        return first;
    }
};
} // end namespace detail

Then your sort function would look something like:

template <typename Iterator, typename Pivot = detail::pivot>
void sort(Iterator first, Iterator last)
{
    if (first >= last) {
        return;
    }

    auto pivot = Pivot().choose_pivot(first, last);
    auto next_pivot = detail::partition(first, last, pivot);
    sort<Iterator, Pivot>(first, next_pivot);
    sort<Iterator, Pivot>(next_pivot + 1, last);
}

A similar pattern can be used for anything else you want to specify.

Note that we've gotten rid of having to specify template parameters (almost) everywhere. In fact, the same can be done in your run_test function:

...
quicksort::sort(std::begin(container), std::end(container));
...

The compiler is smart enough to deduce parameters, so let it do the hard work.

\$\endgroup\$
  • \$\begingroup\$ Is naming the pivot struct pivot a good idea if I want to have multiple pivot choosing algorithms? Would it be better to call that struct something like middle_pivot_selector? \$\endgroup\$ – red_eight Dec 17 '13 at 2:27
  • \$\begingroup\$ @red_eight Sure, middle_pivot_selector would probably be a better name for it. \$\endgroup\$ – Yuushi Dec 17 '13 at 2:34
  • \$\begingroup\$ I have updated my code base on your and @MichaelUrman 's suggestions. The std::partition algorithm does not work correctly for some reason. I'm using std::stable_partition instead, but I'm getting the same incorrect results. When I use my partition method, everything still works fine. \$\endgroup\$ – red_eight Dec 17 '13 at 5:13
  • \$\begingroup\$ @red_eight My apologies with that. When I tested that what I'd written was working, I forgot to specify template parameters for sort (even though I included them above), and it must have switched to using std::sort. \$\endgroup\$ – Yuushi Dec 18 '13 at 6:42
  • \$\begingroup\$ @Yuushi: I don't think your partition function works, because pivot points into the range [first, last) and therefore the value of *pivot will change as the elements are swapped around inside std::partition, which means the lambda you've given to std::partition is not a predicate (it can give two different results for the same inputs). \$\endgroup\$ – Quuxplusone Feb 1 at 18:02
5
\$\begingroup\$

Regarding Driver.cpp's rvalue reference in void run_test (const std::string &name, Container <DataType> &&container), since Container is being deduced, this isn't necessarily an rvalue reference; this could be either an rvalue or lvalue reference. Scott Meyers calls this construct a universal reference and offers advice on how to use them, as well as their pitfalls.

Typically the only place you need to care rvalue references are for implementing move constructors and forwarding functions (the "universal reference" is great for forwarding functions). Outside of those, the rules haven't changed much: take a reference if you want to change things, take a const reference if you don't want to change things, and take it by value if you need to change things internally. The last of these is automatically move-constructed if the type supports it.

And no, while your construct currently looks like one for a forwarding function, your function doesn't really forward anything. So you probably shouldn't be using std::forward (the conditional move) or even std::move (the unconditional rvalue cast) in run_test. This is because the only time you can afford for run_test to move the container is the last line where it calls print_container and print_container only accepts a const reference. Given that, I would probably remove the references entirely - semantically run_test accepts a container and then modifies it internally - it should just accept raw Container<DataType>, and not care whether it was moved or copied to get there.

\$\endgroup\$
  • \$\begingroup\$ +1 For the article. That was a great read, but a tad complicated. Man, passing non-trivial objects by value is going to take time to get used to. \$\endgroup\$ – red_eight Dec 17 '13 at 3:08

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.