Sorting three ways

Question

I have implemented function templates that take a begin and end iterator as well as an optional comparator for user-defined types. It was my intention to mimic the usage of std::sort. The three sorting algorithms I used were bubble sort, selection sort and merge sort. I perform merge sort in place.

#ifndef BRUGLESCO_DATASORTER_SORTING_FUNCTIONS_H
#define BRUGLESCO_DATASORTER_SORTING_FUNCTIONS_H

#include <cstddef>
#include <functional>
#include <iterator>
#include <utility>

namespace bruglesco {
    template <typename RandIterator,
        typename Comparator = std::less<typename std::iterator_traits<RandIterator>::value_type>>
    inline void bubble_sort(RandIterator begin,
        RandIterator end,
        Comparator cmp = Comparator())
    {
        while (begin != end)
        {
            for (auto temp_lhs = begin; temp_lhs != end; ++temp_lhs)
            {
                auto temp_rhs = temp_lhs;
                ++temp_rhs;
                if (temp_rhs != end && !cmp(*temp_lhs, *temp_rhs))
                {
                    std::swap(*temp_lhs, *temp_rhs);
                }
            }
            --end;
        }
    }

    template <typename RandIterator,
        typename Comparator = std::less<typename std::iterator_traits<RandIterator>::value_type>>
    inline void selection_sort(RandIterator begin,
        RandIterator end,
        Comparator cmp = Comparator())
    {
        while (begin != end)
        {
            auto smallest = begin;
            for (auto temp = begin; temp != end; ++temp)
            {
                if (cmp(*temp, *smallest))
                {
                    smallest = temp;
                }
            }
            if (smallest != begin)
            {
                std::swap(*smallest, *begin);
            }
            ++begin;
        }
    }

    template <typename RandIterator,
        typename Comparator = std::less<typename std::iterator_traits<RandIterator>::value_type>>
    inline void merge_sort(RandIterator begin,
        RandIterator end,
        Comparator cmp = Comparator())
    {
        bool unsorted{ true };
        std::size_t size = 0;
        std::size_t sub_size = 1;

        while (unsorted)
        {
            auto lhs = begin;
            auto rhs = begin;

            for (std::size_t i = 0; i < sub_size; ++i)
            {
                ++rhs;
                if (sub_size == 1) { ++size; }
            }

            while (rhs != end)
            {
                std::size_t left_count = sub_size;
                std::size_t right_count = sub_size;
                while (left_count > 0 && right_count > 0)
                {
                    if (rhs == end) { break; }
                    if (cmp(*rhs, *lhs))
                    {
                        auto temp_lhs = rhs;
                        auto temp_rhs = rhs;
                        --temp_lhs;
                        while (temp_rhs != lhs)
                        {
                            std::swap(*temp_lhs, *temp_rhs);
                            --temp_lhs;
                            --temp_rhs;
                        }
                        ++lhs;
                        if (rhs == end) { break; }
                        ++rhs;
                        --right_count;
                        if (sub_size == 1) { ++size; }
                    }
                    else
                    {
                        ++lhs;
                        --left_count;
                    }
                }
                for (std::size_t i = 0; i < left_count; ++i)
                {
                    ++lhs;
                }
                for (std::size_t i = 0; i < right_count; ++i)
                {
                    if (rhs == end || lhs == end) { break; }
                    ++lhs;
                    ++rhs;
                    if (sub_size == 1) { ++size; }
                }
                for (std::size_t i = 0; i < sub_size; ++i)
                {
                    if (rhs == end) { break; }
                    ++rhs;
                    if (sub_size == 1) { ++size; }
                }
            }
            sub_size *= 2;
            if (sub_size > size) { unsorted = false; }
        }
    }
}
#endif // !BRUGLESCO_DATASORTER_SORTING_FUNCTIONS_H

I also have a small usage example:

#include "sorting_functions.h"

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> test_collection{ 2, 97, 849, 38, 2, 13, 17, 2, 2, 22, 9 };

    for (auto& item : test_collection)
    {
        std::cout << item << '\n';
    }

    std::cout << "\nSorting. . . !\n\n";

    //bruglesco::bubble_sort(test_collection.begin(), test_collection.end());

    //bruglesco::merge_sort(test_collection.begin(), test_collection.end());

    //bruglesco::selection_sort(test_collection.begin(), test_collection.end());

    //std::sort(test_collection.begin(), test_collection.end());

    for (auto& item : test_collection)
    {
        std::cout << item << '\n';
    }

    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

---

A couple of things I would love review on.

1. Any glaring mistakes? (I don't feel like my testing is as good as it should be.)
2. Any performance optimizations I can make? *Assume for the sake of discussion that each function needs to represent said algorithm. (The best optimization for bubble sort is of course use a different algorithm.) Also assume that merge-sort needs to be done in-place.
3. I believe I managed to maintain stability(which was not a requirement.) No?
4. Any issues with readability or decisions I should have documented?

Answer 1

Bubble Sort

Are Random-Access Iterators overconstraining the requirements? Looking over the operations, you need to support the following

• begin != end - Inequality comparison for iterators (Forward Iterator)
• temp_lhs = begin - Copy-assignable (Iterator)
• ++temp_lhs - Incrementable (Iterator)
• --end - Prefix decrement (Bidirectional Iterator)
• Multipass (Forward Iterator)

Your bubble_sort supports iterators that are Random Access or Bidirectional.

---

    template <typename BidirIterator, typename Comparator = 
        std::less<typename std::iterator_traits<RandIterator>::value_type>>
    void bubble_sort(...)

Down with typename has been accepted for c++20. Until you have access to that feature, use helper traits to help with the readability.

    template <typename Iterator> 
    using value_type_t = typename std::iterator_traits<Iterator>::value_type;

    template <typename BidirIterator, typename Comparator = 
        std::less<value_type_t<BidirIterator>>>
    void bubble_sort(...)

c++14 introduced transparent comparators. From std::less<>,

The standard library provides a specialization of std::less when T is not specified, which leaves the parameter types and return type to be deduced.

You may omit the type in the comparator and let it be deduced.

    template <typename BidirIterator, typename Comparator = std::less<>>
    void bubble_sort(...)

---

                    std::swap(*temp_lhs, *temp_rhs);

What happens if swap is specialized as a customization point for your dereferenced iterator type? You could use the ADL two-step,

                    using std::swap;
                    swap(*temp_lhs, *temp_rhs);

Or you could use std::iter_swap, which does the two-step and dereference for you.

                    std::iter_swap(temp_lhs, temp_rhs);

You'll notice a pattern where you guard a swap with a comparison check,

if (cmp(rhs, lhs)) {
    std::iter_swap(lhs, rhs);
}

That's a candidate for an algorithm!

template <typename FwdIterator, typename Compare>
bool iter_swap_if(FwdIterator lhs, FwdIterator rhs, Compare cmp) {
    bool result = cmp(*rhs, *lhs);
    if (result) {
        std::iter_swap(lhs, rhs);
    }
    return result;
}

You can write a version of bubble sort for Forward iterators by assigning the known previous to end as your new end. Bubble sort is also nice in that a pass with no swaps means it's sorted and can exit early.

template <typename FwdIterator, typename Compare = std::less<>>
inline void bubble_sort(FwdIterator first, FwdIterator last, Compare cmp = Compare{}) {
    if (first == last || std::next(first) == last) {
        return; 
    }

    for (bool swapped = true; swapped; /* */) {
        swapped = false;
        auto curr = first;
        for (auto next = std::next(curr); next != end; (void)++next, ++curr) {
            swapped |= iter_swap_if(curr, next, cmp);    
        }
        last = curr;
    }
}

---

Selection Sort

As with bubble_sort, Random-Access iterators is overconstraining your iterator requirement.

• begin != end - Inequality comparison for iterators (Forward Iterator)
• smallest = begin - Copy-assignable (Iterator)
• ++begin - Incrementable (Iterator)

So Forward iterator is your requirement.

        while (begin != end) {
            auto smallest = begin;
            for (auto temp = begin; temp != end; ++temp) {
                if (cmp(*temp, *smallest)) {
                    smallest = temp;
                }
            }
            if (smallest != begin) {
                std::swap(*smallest, *begin);
            }
            ++begin;
        }

If you don't want to use std::min_element, then extract the minimum element finding algorithm from your selection_sort and place it into its own abstraction.

        for (; first != last; ++first) {
          // std::iter_swap(first, std::min_element(first, last, cmp));
             auto smallest = std::min_element(first, last, cmp);
             std::iter_swap(first, smallest);
        }

Don't let reinventing-the-wheel prevent you from rewriting or reusing existing abstractions.

---

Bottom-Up Merge Sort

As Martin noted, this is a long function and really could benefit from one abstraction.

    template <typename RandIterator, typename Comparator = std::less<>>
    inline void merge_sort(RandIterator begin, RandIterator end, Comparator cmp = Comparator()) {
        while each successively longer chunk of pow2 is less than length
            for each paired chunk
                inplace_merge(first, mid, last, cmp);
    }

inplace_merge can be reused for top-down merge sort and other merge operations.

---

1. Any glaring mistakes? (I don't feel like my testing is as good as it should be.)

Don't forget about the empty set! merge_sort segfaults when begin and end are equal. Test on containers with varying shape/size characteristics. Think about what possible states your input arguments can possibly be. Use different types (pairs for stability testing). This is what I threw at it.

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

#define TEST_SORT(NAME)                                                         \
template <typename I, typename C = std::less<>>                                 \
void test_ ## NAME (I first, I last, C cmp = C{}) {                             \
    std::cout << #NAME << ":\n";                                                \
    std::for_each(first, last, [](auto t) {                                     \
        bruglesco:: NAME ## _sort(begin(t), end(t), cmp);                       \
        std::cout << std::boolalpha << std::is_sorted(begin(t), end(t)) << ","; \
    });                                                                         \
    std::cout << "\n\n";                                                        \
}     

TEST_SORT(selection)
TEST_SORT(bubble)
TEST_SORT(merge)

#undef TEST_SORT

int main() {
    using C = std::vector<int>;

    auto empty         = C{};
    auto singleton     = C{0};
    auto doubleton     = C{0, 1};
    auto random        = C{6, 4, 1, 5, 8, 2, 3, 0, 9, 7};
    auto ascend        = C{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    auto descend       = C{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    auto one_off       = C{0, 1, 3, 2, 4, 5, 7, 6, 8, 9};
    auto few_unique    = C{0, 1, 2, 0, 1, 2, 0, 1, 2, 0};
    auto organ         = C{5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5};
    auro hill          = C{0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0};

    auto sets = std::vector<C>{empty, singleton, doubleton, random, ascend
                               descend, one_off, few_unique, organ, hill};

    test_selection(begin(sets), end(sets));
    test_bubble(begin(sets), end(sets));
    test_merge(begin(sets), end(sets));
}

2. Any performance optimizations I can make? *Assume for the sake of discussion that each function needs to represent said algorithm. (The best optimization for bubble sort is of course use a different algorithm.) Also assume that merge-sort needs to be done in-place.

• Bubble sort - can return early if no swaps happen during a pass. Also, don't sleep on the performance of bubble sort with small sets of cheap to copy data or are working with nearly sorted data.
• Selection sort - the interval you loop over may be [first, last-1) since the minimum element from [last-1, last) will always be the last remaining element at position last-1.
• Merge sort - Using a buffer for merging reduces the number of comparisons from linearithmic to linear. Bubble/Insertion sort can often be faster on small sets of values. Measure to find the threshold where Bubble or Insertion sort outperform Merge Sort for an adaptive approach.

3. I believe I managed to maintain stability(which was not a requirement.) No?

• Bubble sort - No. The negation on the compare result swaps on equal. You really wanted cmp(*temp_rhs, *temp_lhs).
• Selection sort - No. Rotate instead of swap.
• Merge sort - Yes!

4. Any issues with readability or decisions I should have documented?

Answered in the review.

Answer 2

I'll assume you have tested them enough to say they work for normal situations.

Overall.

Though perfectly fine. Your use on the outer loop "looks" strange. Personally I would replace them with for() loops. But that's just me.

Swap

Your use of swap works for integers and normal built in types. But it may not work for all types (some types have their own swap in their own namespace).

So the idiomatic way to use swap is:

{
    using std::swap;
    swap(a, b);
}

Assuming a and b are type NameSpace::Type. Then if there is a swap function defined NameSpace for type Type then Koning lookup will find it. Otherwise the compiler will find swap in the local scope (imported from std) and use that.

But don't do that. There is a standard swap function for iterators that encapsulates all the above correctly. std::iter_swap().

So rather than:

std::swap(*temp_lhs, *temp_rhs);

use:

std::iter_swap(temp_lhs, temp_rhs);   // Guaranteed correct swap.

Bubble Sort

You missed the standard optimization. If you do a pass and there was zero swaps required in the last past then the container is sorted and you can exit. This great property of bubble sort gives it a best case complexity of O(n) (ie if it is already sorted then its a single pass).

I am sure you can simplify the iterator manipulation so you don't have an extra comparison against end.

Selection Sort

You have an extra comparison against begin every iteration of the outer loop. Then you test to see if begin and smallest are the same at the end of the loop. Not sure that is an optimization or a pessimization. If you have found this to be a general case optimization then you should comment it.

Merge Sort

Looks like it should work.
But writing it all in one method like that hurts my brain. I prefer when it is split into two logical methods. But writing it as one may be a requirement to do everything in place. If so make that point in a comment.

Finaley

What are the performance characteristics of your sort in relation to std::sort?

Answer 3

Martin has given you a good review of the sort code itself; I'll not repeat that. Instead, I'll look at the example usage code, and see how we can adapt that to be a more rigorous test of the functionality.

Firstly, although the visual comparison can be helpful when debugging, it can be tedious to have to inspect the results every time you make changes. Instead, we can make the program self-checking: exit with a success (zero) status if the tests pass, and a non-zero (error) status if any fail:

return !std::is_sorted(test_collection.begin(), test_collection.end());

Another inconvenience is that we must edit the program's source to test each algorithm. It would be helpful if a single program would test all three algorithms in one run. Let's write a helper function to do the repetitive parts, and allow us to re-use the same starting position for each sort:

#include <algorithm>
#include <array>
#include <iostream>

template<class RandomAccessIterator,
         class Comparator = std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>>
bool is_sort_correct(RandomAccessIterator a, RandomAccessIterator b,
                     std::function<void(RandomAccessIterator,RandomAccessIterator, Comparator)> sort,
                     Comparator cmp = Comparator())
{
    sort(a, b, cmp);
    return std::is_sorted(a, b, cmp);
}

int main()
{
    const std::array<int,11> test_collection{ 2, 97, 849, 38, 2, 13, 17, 2, 2, 22, 9 };
    using Iter = typename decltype(test_collection)::iterator;

    auto failure_count = 0u;

    {
        auto result_vector = test_collection;
        failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::bubble_sort<Iter>);
    }

    {
        auto result_vector = test_collection;
        failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::merge_sort<Iter>);
    }

    {
        auto result_vector = test_collection;
        failure_count += !is_sort_correct(result_vector.begin(), result_vector.end(), bruglesco::selection_sort<Iter>);
    }

    return failure_count > 0;
}

It's about this point that we might want to consider moving to a unit-test framework (there are several to choose from). This helps in several ways; the most useful to me are

• improved diagnostics when tests fail (e.g. showing expected and actual values of compared expressions)
• ability to run the same tests many times on different data, and the same data through different tests

At this point, one could add further tests - I'd recommend adding tests of using a non-default comparator argument, and sorting collections of user-defined types. (We'll need a user-defined type anyway, if we want to test the stability of the sort).