Sorting algorithms - Bubble sort

Question

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';
}

Answer 1

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, ...).

Answer 2

Speed

Of course we all know bubble sort is one of the slowest sorting algorithms¹. 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.}

Answer 3

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

Answer 4

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.

Answer 5

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;
        });