1
\$\begingroup\$

I was wondering if this implementation of bubble sort could be improved. Are there any things that I have done wrong?

template<typename Element>
void bubble_sort(Element arr[], size_t size) {
    auto sorted_elements = 1u;
    bool sorted = false;
    while (!sorted) {
        sorted = true;
        for (auto index = 0u; index < size - sorted_elements; ++index) {
            if (arr[index] > arr[index + 1]) {
                auto temp = arr[index + 1];
                arr[index + 1] = arr[index];
                arr[index] = temp;
                sorted = false;
            }
        }
        ++sorted_elements;
    }
}
\$\endgroup\$
2
\$\begingroup\$

Implementation

  • size - sorted_elements might not return what you expect if size == 0 (it returns std::numeric_limits<unsigned int>::max()). This makes the intended check fail for size == 0. This can be fixed by changing the while loops condition to sorted_elements < size && !sorted.
  • You could use std::swap(arr[index], arr[index + 1]); to swap the elements. This way, the preferred assignment operation (copy or move) for Element will be used (if Element provides its own specialization). Currently, you always copy, which might not always be preferred (e.g. with large std::strings).
\$\endgroup\$
  • \$\begingroup\$ Yes you are right I get a runtime error if the size is 0. I did not think about it. Thanks! \$\endgroup\$ – puls99 Nov 14 '17 at 12:02
  • 1
    \$\begingroup\$ @puls99: unsigned and floating point comparisons are always suspect and should be double checked. There are many subtle bugs hidden this way \$\endgroup\$ – hoffmale Nov 14 '17 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.