22
\$\begingroup\$

For pure practice purposes, I started implementing different sorting algorithms in modern C++ in a standard library style way (i.e. using templates on iterators). This is my version of bubble sort.

I do not really have any specific criteria I would like to have the code reviewed under, but instead appreciate any hints I can get, be they on performance, coding style, expressiveness etc.

The whole implementation lives inside the file bubble_sort.h:

#pragma once

#include <utility>

template<typename Iterator, typename Comparator>
void bubble_sort(Iterator begin, Iterator end, Comparator cmp) {
    bool swapped;
    do {
        swapped = false;
        for (auto i = begin + 1; i != end; ++i) {
            auto& val0 = *i;
            auto& val1 = *(i - 1);
            if (cmp(val0, val1)) {
                std::swap(val1, val0);
                swapped = true;
            }
        }
    } while (swapped);
}

template<typename Iterator>
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, [] (const typename Iterator::value_type& v0,
                const typename Iterator::value_type& v1) { return v0 < v1; });
}

For reference, I also provide to you a file containing a main-method which sorts a small std::vector of random unsigneds in ascending as well as descending order:

#include <random>
#include <vector>
#include <iostream>

#include "bubble_sort.h"

int main() {
    std::vector<unsigned> vec;
    std::default_random_engine engine;
    std::uniform_int_distribution<unsigned> distribution(0, 10000);
    for (std::size_t i = 0; i < 100; ++i) {
        unsigned num = distribution(engine);
        std::cout << num  << ' ';
        vec.push_back(num);
    }
    std::cout << "\n\n";

    bubble_sort(vec.begin(), vec.end());

    for (unsigned e : vec) {
        std::cout << e << ' ';
    }
    std::cout << "\n\n";

    bubble_sort(vec.begin(), vec.end(), [] (unsigned v0, unsigned v1) {
            return v0 > v1;
        });

    for (unsigned e : vec) {
        std::cout << e << ' ';
    }
    std::cout << '\n';
}
\$\endgroup\$
11
\$\begingroup\$

I recommend putting your functions into a namespace.


for (auto i = begin + 1; i != end; ++i) {

By doing begin + 1, you require that Iterator is a RandomAccessIterator, whereas you only need an ForwardIterator. Use std::next instead:

for (auto i = std::next(begin); i != end; ++i) {

You could also use std::next(begin, 1) to be explicit.

Similarly, when you do *(i - 1), you require that Iterator is a RandomAccessIterator. Replacing it with std::prev still requires that Iterator is a BidirectionalIterator. Unless you think that is a reasonable requirement (for some versions of bubblesort, it would allow it to be more efficient), don't do this.

Rewrite the for loop as so (or any variant where you keep track of the two):

for (auto i = begin, inext = std::next(begin); inext != end; ++i, ++inext) {
    auto& val0 = *inext;
    auto& val1 = *i;
    // ...

While we are discussing iterator categories, it's useful to name Iterator after the iterator category you require, so FwdIter or ForwardIterator would be better names.


template<typename Iterator>
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, [] (const typename Iterator::value_type& v0,
                const typename Iterator::value_type& v1) { return v0 < v1; });
}

Rather than manually writing out the comparator, use std::less. I would use std::less<>, but you could use std::less<typename std::iterator_traits<Iterator>::value_type> if you wanted to.

template<typename Iterator>
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, std::less<>{});
}

Actually, instead of doing this, you could put a default argument on the other overload of bubble_sort:

template<typename Iterator, typename Comparator = std::less<>>
void bubble_sort(Iterator begin, Iterator end, Comparator cmp = {})

There are two advantages I can think of by doing it this way:

  1. Less code (only one function definition)
  2. You avoid ADL problems

One problem with

template<typename Iterator>
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, std::less<>{});
}

is that the bubble_sort(begin, end, ...) can activate ADL. If Iterator was, let's say, mylibrary::vector<int>::iterator, and if I wrote a bubble_sort in the namespace mylibrary, this bubble_sort call might call the one from the mylibrary namespace instead of the one we intended.

This is not good. As a rule of thumb, when writing generic code, avoid unqualified function calls like bubble_sort(begin, end, ...); instead qualify it with the namespace: ::bubble_sort(begin, end, ...).

\$\endgroup\$
  • \$\begingroup\$ Your use of inext introduced a subtle bug. The sort will now show UB for empty or 1-element vectors. \$\endgroup\$ – FRob Jul 7 '17 at 7:43
  • \$\begingroup\$ @FRob I'm fairly sure I didn't introduce any bugs. The bug for an empty range was caught by another answer, and this version has no problem with ranges of size 1 \$\endgroup\$ – Justin Jul 7 '17 at 7:46
11
\$\begingroup\$

Speed

Of course we all know bubble sort is one of the slowest sorting algorithms1. It turns out, however, that stopping when an iteration is completed without a swap usually adds more overhead than it saves. I did a quick test with this code:

template<typename Iterator, typename Comparator>
void bs2(Iterator begin, Iterator end, Comparator cmp) {
    for (auto j=end; j != begin; --j) {
        for (auto i = begin + 1; i != j; ++i) {
            auto& val0 = *i;
            auto& val1 = *(i - 1);
            if (cmp(val0, val1)) {
                std::swap(val1, val0);
            }
        }
    }
}

This ran around 20-25% faster. Of course, if you actually care about speed, you'd probably want to switch to another algorithm entirely, but if you're going to do a bubble sort, you might as well at least use the variant that's consistently the fastest. There's another variant (often called the shakersort) which alternates between upward and downward iterations. This turns out to be still slower, as a rule.

Iterator dependent types

To find the value type associated with an iterator, you use:

const typename Iterator::value_type&

Instead of this, I'd use:

std::iterator_traits<Iterator>::value_type

For one example, this will allow the code to work with raw pointers as the "iterators", which the original code won't since pointers won't define a value_type member.


1. Short of those like bogosort that were invented specifically to be as slow as possible, of course.

\$\endgroup\$
  • \$\begingroup\$ I am under the impression that bubble sort is actually OK - or potentially preferable due to low overheads - for very small sets of data, or data which is almost in order. \$\endgroup\$ – JWT Jul 6 '17 at 9:45
  • \$\begingroup\$ @JWT, there are better variations of bubble sort, such as shaker sort and comb sort. There is a problem that bubble sort introduces, I believe it is called turtle and rabbit. Do note that comb sort requires <= to work. \$\endgroup\$ – Incomputable Jul 6 '17 at 9:52
  • \$\begingroup\$ @jwt: No. For nearly any situation where a bubble sort might work sort of OK, an insertion sort or selection sort will be better. Of those two, insertion sort is usually preferable, but if you have objects that are much cheaper to compare than to copy (e.g., an int key with a lot of attached data) a selection sort may be better. \$\endgroup\$ – Jerry Coffin Jul 6 '17 at 13:29
  • \$\begingroup\$ I would be very interested in the actual data you gathered while testing. The main point I see for terminating early is, of course, for nearly ordered containers: Suppose you have a large number of items (let's say 10 million), but only one or two of those are out of order. Not terminating early will lead to nearly 10 million redundant iterations, which would likely be a huge speed killer. Of course, I understand that terminating early in the average case might not be beneficial due to optimizations etc. \$\endgroup\$ – Ben Steffan Jul 6 '17 at 14:31
  • \$\begingroup\$ The point about using std::iterator_traits is very good. I will probably switch to your version. \$\endgroup\$ – Ben Steffan Jul 6 '17 at 14:33
11
\$\begingroup\$
std::swap(val1, val0);

This hard codes std::swap as the function to use for swapping. C++ also has a powerful (and sometimes confusing) mechanism to allow multiple namespaces to be searched for a function: argument dependent lookup (ADL).

To make use of it call swap unqualified, which performs ADL to find swap functions in the namespaces of the arguments, but also add std::swap as a "fallback":

using std::swap;
swap(val1, val0);

For further information on why you want this see this SO question as well as the top answer to this one (but don't get confused about it's incorrect references to the points in the question).

Going further, the best approach is to use std::iter_swap(&val1, &val0) as deduplicator suggested. The standard describes its effects as "swap(*a,*b)" (where a and b are the parameters of std::iter_swap) and further imposes the "swappable" requirements, which state:

An object t is swappable with an object u if and only if:

  • the expressions swap(t, u) and swap(u, t) are valid when evaluated in the context described below [..]

The context in which swap(t, u) and swap(u, t) are evaluated shall ensure that a binary non-member function named “swap” is selected via overload resolution [..] on a candidate set that includes:

  • the two swap function templates defined in <utility> [..] and
  • the lookup set produced by argument-dependent lookup [..]

[N4296] §17.6.3.2/2,3

\$\endgroup\$
  • \$\begingroup\$ @DanielJour Thank you. I did not know about this "trick" (although, in hindsight, it seems kind of obvious). \$\endgroup\$ – Ben Steffan Jul 6 '17 at 14:27
10
\$\begingroup\$

I'll add this since nobody mentioned it: the code will cause undefined behavior on empty ranges.

Th reason is that i != end will not properly work since i is initialized with i + 1.

I recommend just doing the check at the beginning and returning if std::distance(begin, end) is less than two.

\$\endgroup\$
  • \$\begingroup\$ With the distance computed with std::distance, ideally. \$\endgroup\$ – Daniel Jour Jul 6 '17 at 5:22
  • \$\begingroup\$ @DanielJour, I meant that, but probably making more explicit is worth it. Thanks \$\endgroup\$ – Incomputable Jul 6 '17 at 5:23
  • \$\begingroup\$ @Incomputable Thanks, I totally didn't think about that edge case! \$\endgroup\$ – Ben Steffan Jul 6 '17 at 14:26
  • \$\begingroup\$ @BenSteffan, I recommend setting up a test. Just create new randomized vector in a loop, sort it, use std::is_sorted, from size 0 to 75'000. Every increment of the upper bound will increase runtime seriously. This should be pretty easy to setup. \$\endgroup\$ – Incomputable Jul 6 '17 at 14:29
  • \$\begingroup\$ @Incomputable In what context? I don't think your answer talks about speed (or time complexity), and neither do any of the comments. \$\endgroup\$ – Ben Steffan Jul 6 '17 at 14:39
8
\$\begingroup\$

I can't see anything in the sort that other have not already commented on. But lets have a look at your main:

Prefer to use std::begin() and std::end() rather than member functions. This will keep your code generic so that if you switch to using C arrays for vec the code will continue to work.

    bubble_sort(vec.begin(), vec.end());

    // Like this:
    bubble_sort(std::begin(vec), std::end(vec));

When using range based loops prefer to use the auto type. This way if you change the underlying type of the container you don't need to change the for loop as this will adapt to the container content.

    for (unsigned e : vec) {
        std::cout << e << ' ';
    }

    // Like this:
    for (auto const& e : vec) {
        std::cout << e << ' ';
    }

Another useful place to use auto is in lambda parameter values.

    bubble_sort(std::begin(vec), std::end(vec), [] (auto const& v0, auto const& v1) {
            return v0 > v1;
        });
\$\endgroup\$
  • \$\begingroup\$ Thank you for your review. I just wrote the main-method as a quick test, not giving very much attention on good coding practices and the like. Still, I have to admit that I didn't even know there were non-member std::begin and std::end, so that at least will likely become useful (I do know about auto, but I tend to prefer to write out most of the typenames, because it makes the code easier to read in my opinion (still, your point about changing the underlying type is of course valid)). \$\endgroup\$ – Ben Steffan Jul 6 '17 at 14:38
  • 1
    \$\begingroup\$ @BenSteffan I agree you should always be explicit about typing (where it matters). The use of auto should be reserved for locations were the type does not matter explicitly but can be inferred. (range based for and lambda are the most obvious of those). \$\endgroup\$ – Martin York Jul 6 '17 at 20:47

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.