Bubble sort

bubble-sort.cpp

#include <iterator> // bidirectional_iterator, iterator_traits
#include <utility>  // move, swap

template <std::bidirectional_iterator BidirectionalIterator, typename Compare,
          typename ValueType =
              typename std::iterator_traits<BidirectionalIterator>::value_type>
constexpr auto bubble_sort1(BidirectionalIterator begin,
                            BidirectionalIterator end, Compare compare)
    -> void {
  if (begin == end) {
    return;
  }

  bool swapped = false;

  for (BidirectionalIterator i = begin; i != end; end -= 1) {
    swapped = false;

    for (BidirectionalIterator j = begin + 1; j != end; ++j) {
      ValueType &lhs = *(j - 1);
      ValueType &rhs = *j;

      if (compare(lhs, rhs) > 0) {
        std::swap(lhs, rhs);
        swapped = true;
      }
    }

    if (swapped == false) return;
  }
}

template <std::bidirectional_iterator BidirectionalIterator, typename Compare,
          typename ValueType =
              typename std::iterator_traits<BidirectionalIterator>::value_type>
constexpr auto bubble_sort2(BidirectionalIterator begin,
                            BidirectionalIterator end, Compare compare)
    -> void {
  if (begin == end) {
    return;
  }

  for (BidirectionalIterator i; begin != end; end = i) {
    i = begin;

    for (BidirectionalIterator j = begin + 1; j != end; ++j) {
      ValueType &lhs = *(j - 1);
      ValueType &rhs = *j;

      if (compare(lhs, rhs) > 0) {
        std::swap(lhs, rhs);
        i = j;
      }
    }
  }
}