Sorting algorithms - Bubble sort 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 &lt;utility&gt;

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

template&lt;typename Iterator&gt;
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, [] (const typename Iterator::value_type&amp; v0,
                const typename Iterator::value_type&amp; v1) { return v0 &lt; 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 &lt;random&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;

#include "bubble_sort.h"

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

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

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

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

    for (unsigned e : vec) {
        std::cout &lt;&lt; e &lt;&lt; ' ';
    }
    std::cout &lt;&lt; '\n';
}
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&amp; val0 = *inext;
    auto&amp; 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&lt;typename Iterator&gt;
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, [] (const typename Iterator::value_type&amp; v0,
                const typename Iterator::value_type&amp; v1) { return v0 &lt; v1; });
}



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

template&lt;typename Iterator&gt;
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, std::less&lt;&gt;{});
}


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

template&lt;typename Iterator, typename Comparator = std::less&lt;&gt;&gt;
void bubble_sort(Iterator begin, Iterator end, Comparator cmp = {})


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


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


One problem with

template&lt;typename Iterator&gt;
void bubble_sort(Iterator begin, Iterator end) {
    bubble_sort(begin, end, std::less&lt;&gt;{});
}


is that the bubble_sort(begin, end, ...) can activate ADL. If Iterator was, let's say, mylibrary::vector&lt;int&gt;::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, ...).