2
\$\begingroup\$

A collection of sorting types as following insertion, radix, selection and heap sorts.

How can i improve it?

#include <algorithm>
#include <functional>
#include <type_traits>
#include <iostream>


template <typename Iterator>
void radixSort(Iterator begin, Iterator end)
{
    using value_type = typename std::iterator_traits<Iterator>::value_type;

    for (auto i = 0; i < 32; ++i)
    {
        std::stable_partition(begin, end,
            [&](value_type& value)
        {
            if (i == 31) 
                return value < 0; 
            else
                return !(value & (1 << i));
        });
    }
}

template<typename Iterator>
void insertionSort(Iterator begin, Iterator end)
{
    using value_type = typename std::iterator_traits<Iterator>::value_type;

    for (auto i = begin; i != end; ++i)
    {
        std::rotate(std::upper_bound(begin, i, *i, std::less<value_type>()), i, std::next(i));
    }
}

template <typename Iterator>
void selectionSort(Iterator begin, Iterator end)
{
    using value_type = typename std::iterator_traits<Iterator>::value_type;

    for (; begin != end; ++begin)
    {
        const auto minElemt(std::min_element(begin, end, std::less<value_type>()));

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

template <typename Iterator>
void heapSort(Iterator begin, Iterator end)
{
    using value_type = typename std::iterator_traits<Iterator>::value_type;

    std::make_heap(begin, end, std::less<value_type>());
    std::sort_heap(begin, end, std::less<value_type>());
}

int main()
{
    int a[] = {9,-6, 7, -8, 6, -9, 1, 3, -4, 2, -1, -5, 5, 8, -3, 4, 0, -2, -7 };

    radixSort(std::begin(a), std::end(a));
    //insertionSort(std::begin(a), std::end(a));
    //selectionSort(std::begin(a), std::end(a));
    //heapSort(std::begin(a), std::end(a));

    for (const auto& i : a)
    {
        std::cout << i << ' ';
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Your radixSort implicitly assumes that all value_types are 32-bit signed integers, I would recommend something like static_assert(std::is_same<value_type, int32_t>::value, "Wrong type"); and to make it work for more types. \$\endgroup\$
    – nwp
    Jan 9, 2015 at 14:42
  • \$\begingroup\$ @nwp good point. i will do it \$\endgroup\$
    – MORTAL
    Jan 9, 2015 at 14:53

1 Answer 1

2
\$\begingroup\$

In radixSort you assume that std::iterator_traits<Iterator>::value_type is a signed 32bit int.

Instead you should check whether it's an integral type and alter the algorithm a bit based on its properties:

template <typename Iterator>
void radixSort(Iterator begin, Iterator end)
{
    using value_type = typename std::iterator_traits<Iterator>::value_type;

    static_assert(std::numeric_limits<value_type>::is_integer, "Wrong type");

    for (auto i = 0; i < std::numeric_limits<value_type>::digits; ++i)
    {
        std::stable_partition(begin, end,
            [&](value_type& value)
        {
             return !(value & (1 << i));
        });
    }

    if(std::numeric_limits<value_type>::is_signed){
        std::stable_partition(begin, end,
            [&](value_type& value)
        {
             return value < 0;
        });
    }

}

Besides that all your algorithms use the standard std::less comparator. you should let the user supply a comparator (a mapping function for radixSort) for types that don't have a default std::less.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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