bubble sort implementation in c++

Question

the code below is used to implement bubble sort. why is template used in this case? and what is the purpose of swapped variabe. even if i remove swapped variable and swapped condition from loop code still works fine

#include <algorithm>
#include <iostream>
#include <iterator>

template <typename RandomAccessIterator>
void bubble_sort(RandomAccessIterator begin, RandomAccessIterator end) {
  bool swapped = true;
  while (begin != end-- && swapped) {
    swapped = false;
    for (auto i = begin; i != end; ++i) {
      if (*(i + 1) < *i) {
        std::iter_swap(i, i + 1);
        swapped = true;
      }
    }
  }
}

int main() {
  int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199};
  bubble_sort(std::begin(a), std::end(a));
  copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\n";
}

ANOTHER IMPLEMENTATION:

template<typename Iterator>
 void bubbleSort(Iterator first, Iterator last)
 {
     Iterator i, j;
     for (i = first; i != last; i++)
         for (j = first; j < i; j++)
             if (*i < *j)
                 std::iter_swap(i, j); // or std::swap(*i, *j);
 }

Answer 1

Different containers have their own iterator types. For example for one-dimensional arrays there are used pointers as iterators while for objects of the type std::vector there are used iterators defined in this template class.

The variable swapped is used as a criteria whether the elements are already sorted. If there was not swapping of elements of the sequence when it was traversed then it means that the sequence is already sorted.

Take into account that the implementation you showed has undefined behavior due to this statement

while (begin != end-- && swapped) {
                ^^^^

because there is an attempt to decrement the last iterator when the range can be empty. So the implementation is incorrect.

Moreover the algorithm is not efficient. For example a tail of the array can be already sorted after some iteration of the internal loop. However in the external loop the last iterator is moved left only one position.

It is enough to use forward iterators for the bubble sort. In this case you can use the algorithm even with std::forward_list and others containers that do not have random access iterators.

Here is a demonstrative program that shows how the algorithm can be implemented using forward iterators.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <forward_list>

template <typename ForwardIterator>
void bubble_sort( ForwardIterator first, ForwardIterator last )
{
    for ( ForwardIterator sorted = first; first != last; last = sorted )
    {
        sorted = first;
        for ( ForwardIterator current = first, prev = first; ++current != last; ++prev )
        {
            if ( *current < *prev )
            {
                std::iter_swap( current, prev );
                sorted = current;
            }
        }
    }
}

int main() 
{
    int a[] = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 };

    bubble_sort( std::begin( a ), std::end( a ) );
    std::copy( std::begin( a ), std::end( a ), 
               std::ostream_iterator<int>( std::cout, " " ) );
    std::cout << "\n";

    std::forward_list<int> lst = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 };

    bubble_sort( std::begin( lst ), std::end( lst ) );
    std::copy( std::begin(lst ), std::end( lst ), 
               std::ostream_iterator<int>( std::cout, " " ) );
    std::cout << "\n";
}   

The program output is

-199 -52 2 3 33 56 99 100 177 200 
-199 -52 2 3 33 56 99 100 177 200 

Here in the program there are used an array and an object of the type std::forward_list and the algorithm can be applied to the both containers.