#ifndef BUBBLE_SORT_H
#define BUBBLE_SORT_H

#include <algorithm>
    
template <class RandomAccessIterator>
void bubble_sort(RandomAccessIterator first, RandomAccessIterator last)
{
    bool finished = false;
    RandomAccessIterator it, end = last - 1;
    while (!finished) {
        bool changed = false;
        for (it = first; it < end; ++it) {
            if (*it > *(it + 1)) {
                std::swap(*it, *(it + 1));
                changed = true;
            }
        }
        if (changed) {
            --end;
        }
        else {
            finished = true;
        }
    }
}

#endif // BUBBLE_SORT_H