Bubble Sort In C++

Question

I'm learning modern C++ and also algorithms, and am doing some practice by coding up some simple algorithms. Also trying to use templates whenever possible as I'm quite unfamiliar with generic programming.

Would like some help in reviewing the code in terms of design, efficiency, conciseness, and style. Please do not hold back and rip my code apart. It's the best way for me to learn :) thank you! I'm using MSVC, C++17.

// version for contaners with random access
// move minima to correct position (sweep from right to left)
template<typename T>
void bubbleRandCppStl(T& container) {
 for (auto i{ container.rend() - 1 }; i != container.rbegin(); --i) {
 bool swapped {}; // flag to store if swap occured in sweep
 for (auto j{ container.rbegin() }; j != i; ++j) {
 if (*j < *(j + 1)) {
 std::iter_swap(j, j + 1);
 swapped = true;
 }
 }
 if (!swapped) { // end early if no swap occurred in sweep
 break;
 }
 }
}
// version for lists (std::list and std::forward_list)
// move maxima to correct position (sweep from left to right, because forward iterator is unidirectional)
template<typename T>
void bubbleListCppStl(T& container) {
 // container.size() takes O(n) time, so we just do a full sweep
 // and get the size at the same time
 typename T::size_type sz{};
 bool swapped{}; // flag to store if swap occured in sweep
 for (auto i{ container.begin() }, after_i{ ++container.begin() };
 after_i != container.end(); ++i, ++after_i) {
 ++sz;
 if (*i > * after_i) {
 std::iter_swap(i, after_i);
 swapped = true;
 }
 }
 if (!swapped) { // end early if no swap occurred in sweep
 return;
 }
 // decrement size as we now need to sort only sz - 1 elements
 --sz;
 // sort the remaining elements
 for (; sz > 1; --sz) {
 auto i{ container.begin() };
 for (auto elem_left{ sz }; elem_left > 1; --elem_left, ++i) {
 if (*i > * (std::next(i))) {
 std::iter_swap(i, std::next(i));
 swapped = true;
 }
 }
 if (!swapped) { // end early if no swap occurred in sweep
 break;
 }
 }
}
```

• Loki Astari: Not sure why you need different algorithms for this. Don't quite understand why the random access iterator version is more efficient.

Answer 1

Welcome to Code Review. Here's some suggestions:

• Instead of taking a container as argument, take a pair of iterators for flexibility.

• Provide one function that uses iterator_category to find the correct version.

• Allow the user to specify a custom comparator.

• Personally, I'd say that bool swapped{false}; is clearer than bool swapped{}.

• Constantly swapping seems less efficient than moving.

• Are you sure you need reverse iterators here? Just traversing from left to right seems fine.

• Calculating std::next(i) twice doesn't feel efficient.