Bubble Sort Algorithm in C++

1. Implement Bubble Sort for std::vector Container
2. Analyze Bubble Sort Complexity with Empirical Timing Measurements

This article will explain several methods of how to implement the bubble sort algorithm in C++.

Implement Bubble Sort for std::vector Container

Bubble sort is one of the simplest sorting algorithms. It iterates through the list of objects comparing each adjacent pairs, and if they are not ordered, the elements are swapped. It’s classified as a comparison sort algorithm, as the only reading of the elements is done using the comparison expression. In the following example code, we implement bubble sort to work on generic vector objects. A single function named bubbleSort is sufficient enough to define the whole sorting routine. The function is templatized and takes a reference to a vector as the only argument.

bubbleSort includes two nested for loops to iterate over the vector elements until they are sorted in ascending order. Note that each iteration of the outer for loop stores one element in a correct place. The latter element is stored at the end of the vector, and it happens to be the largest element in the part of the vector that is traversed in the inner loop. Notice that we utilized the std::swap algorithm to simplify the implementation and make it more readable.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void bubbleSort(vector<T> &vec) {
  for (size_t i = 0; i < vec.size() - 1; ++i) {
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
      if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
    }
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  bubbleSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

Analyze Bubble Sort Complexity with Empirical Timing Measurements

Bubble sort belongs to a quadratic running-time class. In fact, the average time and worst-case performance of this algorithm both are quadratic - O(n²). Thus, this method becomes utterly inefficient for large input data sets. It’s not used practically for this very reason. E.g., if we increase the input vector length by 10, the running time will grow roughly by a factor of 100. Note, though, bubble sort can be quite efficient for a special case when elements in the input vector are out of order by only one place (e.g., 1032547698 sequence). The latter case would make the algorithm complexity linear. The following code example measures the running time for two different vectors using the gettimeofday function and outputs the results to the console.

#include <sys/time.h>

#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void bubbleSort(vector<T> &vec) {
  for (size_t i = 0; i < vec.size() - 1; ++i) {
    for (size_t j = 0; j < vec.size() - i - 1; ++j) {
      if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
    }
  }
}

float time_diff(struct timeval *start, struct timeval *end) {
  return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}

int main() {
  struct timeval start {};
  struct timeval end {};

  vector<int> vec3(100, 10);
  vector<int> vec4(1000, 10);

  gettimeofday(&start, nullptr);
  bubbleSort(vec3);
  gettimeofday(&end, nullptr);
  printf("bubbleSort %zu elements: %0.8f sec\n", vec3.size(),
         time_diff(&start, &end));

  gettimeofday(&start, nullptr);
  bubbleSort(vec4);
  gettimeofday(&end, nullptr);
  printf("bubbleSort %zu elements: %0.8f sec\n", vec4.size(),
         time_diff(&start, &end));

  return EXIT_SUCCESS;
}

Output:

bubbleSort 100 elements: 0.00002500 sec
bubbleSort 1000 elements: 0.00184900 sec