2
\$\begingroup\$

I've implemented selection sort, heap sort, insertion sort, and iterative quicksort using C++11. Am I using the correct STL data structures/algorithms? Am I using move semantics correctly in my code?

#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <iterator>
#include <utility>
#include <stack>

namespace detail
{    
    template <typename It, typename Comp>
    void heapSort(It begin, It end, Comp compFunc, std::random_access_iterator_tag)
    {
        std::make_heap(begin, end, compFunc);
        std::sort_heap(begin, end, compFunc);
    }

    template <typename It, typename Comp, typename IterCat>
    void heapSort(It begin, It end, Comp compFunc, IterCat)
    {
        typedef typename It::value_type value_type;

        std::vector<value_type> randomAccessContainer(std::make_move_iterator(begin), std::make_move_iterator(end));
        heapSort(std::begin(randomAccessContainer), std::end(randomAccessContainer), compFunc, std::random_access_iterator_tag());
        std::move(std::begin(randomAccessContainer), std::end(randomAccessContainer), begin);
    }

    template <typename It>
    class QuicksortStack
    {
    private:
        typedef std::pair<It, It> IterRange;
        std::stack<IterRange> m_stack;
    public:
        void push(IterRange&& range)
        {
            if (std::distance(range.first, range.second) >= 2)
            {
                m_stack.push(std::move(range));
            }
        }

        void push(const IterRange& range)
        {
            if (std::distance(range.first, range.second) >= 2)
            {
                m_stack.push(range);
            }
        }

        void pop()
        {
            m_stack.pop();
        }

        IterRange top() const
        {
            return m_stack.top();
        }

        bool empty() const
        {
            return m_stack.empty();
        }
    };
}

template <typename It, typename Comp>
void selectionSort(It begin, It end, Comp compFunc)
{
    for (; begin != end; ++begin)
    {
        const It minElem(std::min_element(begin, end, compFunc));

        if (begin != minElem)
        {
            std::iter_swap(begin, minElem);
        }
    }
}

template <typename It>
void selectionSort(It begin, It end)
{
    selectionSort(begin, end, std::less<typename It::value_type>());
}

template <typename It, typename Comp>
void heapSort(It begin, It end, Comp compFunc)
{
    detail::heapSort(begin, end, compFunc, typename std::iterator_traits<It>::iterator_category());
}

template <typename It>
void heapSort(It begin, It end)
{
    heapSort(begin, end, std::less<typename It::value_type>());
}

template <typename It, typename Comp>
void insertionSort(It begin, It end, Comp compFunc)
{
    if (std::distance(begin, end) < 2)
    {
        return;
    }

    It elem(std::next(begin));
    It nextElem(std::next(elem));
    for (; nextElem != end; ++nextElem)
    {
        std::inplace_merge(begin, elem, nextElem, compFunc);
        elem = nextElem;
    }

    std::inplace_merge(begin, elem, nextElem, compFunc);
}

template <typename It>
void insertionSort(It begin, It end)
{
    insertionSort(begin, end, std::less<typename It::value_type>());
}

template <typename It, typename Comp>
void quickSort(It begin, It end, Comp compFunc)
{
    detail::QuicksortStack<It> ranges;
    ranges.push(std::make_pair(begin, end));

    while (!ranges.empty())
    {
        const auto current(ranges.top());
        ranges.pop();

        const It last(std::prev(current.second));
        const It pivot(std::partition(current.first, last, [=](const typename It::value_type& val){ return compFunc(val, *last); }));
        std::iter_swap(pivot, last);

        ranges.push(std::make_pair(current.first, pivot));

        if (pivot != current.second)
        {
            ranges.push(std::make_pair(std::next(pivot), current.second));
        }
    }
}

template <typename It>
void quickSort(It begin, It end)
{
    quickSort(begin, end, std::less<typename It::value_type>());
}

Edit: Updated to reflect Dave's answer, below.

#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <iterator>
#include <utility>
#include <stack>
#include <iostream>

namespace detail
{    
    template <typename RandIt, typename Comparer>
    void heapSort(RandIt begin, RandIt end, Comparer compFunc, std::random_access_iterator_tag)
    {
        std::make_heap(begin, end, compFunc);
        std::sort_heap(begin, end, compFunc);
    }

    template <typename FwdIt, typename Comparer, typename IterCat>
    void heapSort(FwdIt begin, FwdIt end, Comparer compFunc, IterCat)
    {
        typedef typename std::iterator_traits<FwdIt>::value_type value_type;

        std::vector<value_type> randomAccessContainer(std::make_move_iterator(begin), std::make_move_iterator(end));
        heapSort(std::begin(randomAccessContainer), std::end(randomAccessContainer), compFunc, std::random_access_iterator_tag());
        std::move(std::begin(randomAccessContainer), std::end(randomAccessContainer), begin);
    }

    template <typename InIt>
    class QuicksortStack
    {
    private:
        typedef std::pair<InIt, InIt> IterRange;
        std::stack<IterRange> m_stack;
    public:
        void push(IterRange&& range)
        {
            if (std::distance(range.first, range.second) >= 2)
            {
                m_stack.push(std::move(range));
            }
        }

        void push(const IterRange& range)
        {
            if (std::distance(range.first, range.second) >= 2)
            {
                m_stack.push(range);
            }
        }

        void pop()
        {
            m_stack.pop();
        }

        IterRange top() const
        {
            return m_stack.top();
        }

        bool empty() const
        {
            return m_stack.empty();
        }
    };
}

template <typename FwdIt, typename Comparer>
void selectionSort(FwdIt begin, FwdIt end, Comparer compFunc)
{
    for (; begin != end; ++begin)
    {
        const auto minElem(std::min_element(begin, end, compFunc));

        if (begin != minElem)
        {
            std::iter_swap(begin, minElem);
        }
    }
}

template <typename FwdIt>
void selectionSort(FwdIt begin, FwdIt end)
{
    selectionSort(begin, end, std::less<typename std::iterator_traits<FwdIt>::value_type>());
}

template <typename FwdIt, typename Comparer>
void heapSort(FwdIt begin, FwdIt end, Comparer compFunc)
{
    detail::heapSort(begin, end, compFunc, typename std::iterator_traits<FwdIt>::iterator_category());
}

template <typename FwdIt>
void heapSort(FwdIt begin, FwdIt end)
{
    heapSort(begin, end, std::less<typename std::iterator_traits<FwdIt>::value_type>());
}

template <typename FwdIt, typename Comparer>
void insertionSort(FwdIt begin, FwdIt end, Comparer compFunc)
{
    for (auto elem = begin; elem != end; ++elem)
    {
        const auto current(std::move(*elem));
        const auto sortPosition(std::upper_bound(begin, elem, current, compFunc));

        std::move_backward(sortPosition, elem, std::next(elem));

        *sortPosition = std::move(current);
    }
}

template <typename FwdIt>
void insertionSort(FwdIt begin, FwdIt end)
{
    insertionSort(begin, end, std::less<typename std::iterator_traits<FwdIt>::value_type>());
}

template <typename BiDirIt, typename Comparer>
void quickSort(BiDirIt begin, BiDirIt end, Comparer compFunc)
{
    detail::QuicksortStack<BiDirIt> ranges;
    ranges.push(std::make_pair(begin, end));

    while (!ranges.empty())
    {
        const auto current(ranges.top());
        ranges.pop();

        const auto last(std::prev(current.second));
        const auto pivot(std::partition(current.first, last, [=](const typename std::iterator_traits<BiDirIt>::value_type& val){ return compFunc(val, *last); }));
        std::iter_swap(pivot, last);

        ranges.push(std::make_pair(current.first, pivot));

        if (pivot != current.second)
        {
            ranges.push(std::make_pair(std::next(pivot), current.second));
        }
    }
}

template <typename BiDirIt>
void quickSort(BiDirIt begin, BiDirIt end)
{
    quickSort(begin, end, std::less<typename std::iterator_traits<BiDirIt>::value_type>());
}
\$\endgroup\$
4
\$\begingroup\$

Your code looks good, I don't see any major problems.

Here's what I would consider changing:

  • Name your iterator template arguments by the iterator concept they are required to meet. For example: template<typename ForwardIt>
  • I would prefer not to see early returns from functions if possible. I think it's clearer to do if(blah){ do stuff } then to do if(!blah){ return; } do stuff
  • I didn't look closely at all of them, but you can use STL to make a much prettier insertion sort:

....

template<typename ForwardIt, typename Compare>
void InsertionSort(ForwardIt first, ForwardIt last, Compare comp)
{
    for(auto i = first; i != last; ++i)
    {
        std::rotate(std::upper_bound(first, i, *i, comp), i, std::next(i));
    }
}

Edit: In hindsight, that insertion sort is sub optimal. Yours will be quite bad too. Here's a much faster one, with different STL use:

template<typename BiDirIt, typename Compare>
void InsertionSort(BiDirIt first, BiDirIt last, Compare comp)
{
    for(auto i = first; i != last; ++i)
    {
        auto current = std::move(*i);
        auto start   = std::upper_bound(first, i, current, comp);
        std::move_backward(start, i, std::next(i));
        *start       = std::move(current);
    }
}

Edit2: Your forwarding functions (the functions that fill in a default compare function) don't allow for raw pointer iterators. The STL algorithms do. The problem is that you're using typename FwdIt::value_type. Obviously a raw pointer doesn't have a member typedef called value_type. The way to solve this is to use iterator_traits:

template <typename FwdIt>
void selectionSort(FwdIt begin, FwdIt end)
{
    selectionSort(begin, end, std::less<typename std::iterator_traits<FwdIt>::value_type>());
}
\$\endgroup\$

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.