Skip to content

Instantly share code, notes, and snippets.

@airglow923
Created November 10, 2021 16:31
Show Gist options
  • Save airglow923/77a1d245c1f12db57cefce802ce87dbe to your computer and use it in GitHub Desktop.
Save airglow923/77a1d245c1f12db57cefce802ce87dbe to your computer and use it in GitHub Desktop.
Bubble sort
#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;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment