Implementation of Bubble Sort Algorithm in C++

Bubble sort is a simple sorting algorithm that repeatedly iterates through all elements in a given list, compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, which indicates that the list is sorted. In this article, we’ll start with a basic version of the bubble sort algorithm in C++ to sort a list of numbers in ascending order. We’ll then explore several variations, including sorting in descending order and sorting custom objects.

Prerequisites:

Basic Bubble Sort Implementation

Let’s begin with the standard iterative implementation of bubble sort. This version sorts an array in ascending order by repeatedly comparing adjacent elements and swapping them if they are in the wrong order.

#include <iostream>
#include <vector>

// Function to perform bubble sort on a vector of integers
void bubbleSort(std::vector<int>& arr) {
  int n = arr.size(); // Get the size of the array

  // Outer loop: iterates through the array n-1 times
  // After each pass, the largest unsorted element "bubbles up" to its correct position
  for (int i = 0; i < n - 1; i++) {

    // Inner loop: compares adjacent elements and swaps them if they are in the wrong order
    // The range of the inner loop decreases by 1 in each pass of the outer loop
    for (int j = 0; j < n - i - 1; j++) {

      // Compare the current element with the next element
      if (arr[j] > arr[j + 1]) {
        // If the current element is greater than the next element, swap them

        // Swap arr[j] and arr[j+1] using a temporary variable
        int temp = arr[j];   // Store the value of arr[j] in temp
        arr[j] = arr[j + 1]; // Assign the value of arr[j+1] to arr[j]
        arr[j + 1] = temp;   // Assign the value of temp (originally arr[j]) to arr[j+1]
      }
    }
  }
}

int main() {
  std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};

  bubbleSort(arr); // Call the bubbleSort function to sort the array

  std::cout << "Sorted array: \n";

  // Iterate through the sorted array and print each element
  for (int i = 0; i < arr.size(); i++)
    std::cout << arr[i] << " "; // Print the element followed by a space

  std::cout << std::endl;

  return 0;
}

Explanation:

  • We start by including the necessary header files: iostream for input/output operations and vector for using dynamic arrays.
  • The bubbleSort function takes a vector of integers arr as input.
  • n stores the size of the array.
  • The outer loop iterates from i = 0 to n - 2. Each pass makes sure the largest unsorted element “bubbles up” to its correct spot at the end of the array.
  • The inner loop goes from j = 0 to n - i - 2, comparing items that are next to each other.
  • If arr[j] is bigger than arr[j + 1], they are swapped using a temporary variable temp.
  • The main() function creates an example array, calls bubbleSort, and prints the sorted array to the console.

Sorting in Descending Order

To sort from largest to smallest, you only need to change the comparison in the inner loop.

#include <iostream>
#include <vector>

void bubbleSortDescending(std::vector<int>& arr) {
  int n = arr.size();
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] < arr[j + 1]) {
        // Swap arr[j] and arr[j+1]
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

int main() {
  std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
  bubbleSortDescending(arr);
  std::cout << "Sorted array (descending order): \n";
  for (int i = 0; i < arr.size(); i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  return 0;
}

The main difference here is the if (arr[j] < arr[j + 1]) condition. Instead of swapping if the current element is greater than the next, we swap if it’s less than the next, effectively sorting in reverse order.

Optimized Bubble Sort

We can make bubble sort faster by stopping it early if no swaps happen during a pass. If no swaps occur, it means the array is already sorted.

#include <iostream>
#include <vector>

void optimizedBubbleSort(std::vector<int>& arr) {
  int n = arr.size();
  bool swapped;
  for (int i = 0; i < n - 1; i++) {
    swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap arr[j] and arr[j+1]
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
    // If no two elements were swapped in inner loop, the array is sorted
    if (swapped == false)
      break;
  }
}

int main() {
  std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
  optimizedBubbleSort(arr);
  std::cout << "Sorted array (optimized): \n";
  for (int i = 0; i < arr.size(); i++)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
  return 0;
}

Explanation of the Optimization:

  • A boolean variable swapped is used. It starts as false at the beginning of each pass (outer loop).
  • If a swap happens in the inner loop, swapped becomes true.
  • After each pass, if swapped is still false, no swaps were made. This means the array is sorted as all adjacent elements are relatively in order, and we can stop the outer loop using break.

Sorting Custom Objects

To sort objects you’ve created, you need to tell C++ how to compare them. Let’s create a Person class and use a lambda expression to define the sorting criteria. This approach offers flexibility by allowing you to define the comparison logic directly within the sorting function call, without modifying the class itself.

#include <iostream>
#include <vector>
#include <string>

class Person {
public:
  std::string name;
  int age;

  Person(std::string name, int age) : name(name), age(age) {}
};

std::ostream& operator<<(std::ostream& os, const Person& person) {
  os << person.name << " (" << person.age << ")";
  return os;
}

void bubbleSortCustom(std::vector<Person>& arr, auto comparisonFunction) {
  int n = arr.size();
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (comparisonFunction(arr[j], arr[j + 1])) {
        // Swap arr[j] and arr[j+1]
        Person temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

int main() {
  std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35},
    {"David", 20}
  };

  std::cout << "Original array:\n";
  for (const auto& person : people) {
    std::cout << person << "\n";
  }

  // Sort by age using a lambda expression
  bubbleSortCustom(people, [](const Person& a, const Person& b) {
    return a.age > b.age;
  });

  std::cout << "\nSorted array by age:\n";
  for (const auto& person : people) {
    std::cout << person << "\n";
  }

    // Sort by name using a lambda expression
  bubbleSortCustom(people, [](const Person& a, const Person& b) {
    return a.name > b.name;
  });

    std::cout << "\nSorted array by name:\n";
  for (const auto& person : people) {
    std::cout << person << "\n";
  }

  return 0;
}

/*
Output:
Sorted array by age:
David (20)
Bob (25)
Alice (30)
Charlie (35)

Sorted array by name:
Alice (30)
Bob (25)
Charlie (35)
David (20)
*/

Key points:

  • We create a Person class with name and age attributes.
  • Instead of overloading the > operator, the bubbleSortCustom function now accepts a comparisonFunction as a parameter. This function determines how two Person objects are compared.
  • A lambda expression is used when calling bubbleSortCustom to define the comparison logic inline. For example, [](const Person& a, const Person& b) { return a.age > b.age; } sorts the Person objects by age in descending order. We can easily change it to sort by name [](const Person& a, const Person& b) { return a.name > b.name; }.
  • The bubbleSortCustom function is similar to the basic bubble sort, but it now works with a vector of Person objects and uses the provided comparisonFunction to compare the Person objects.
  • In the main() function, we create a vector of Person objects, sort them using bubbleSortCustom with a lambda expression, and print the sorted list.

What’s Next?

Now that you’ve learned how to implement bubble sort in C++, you might want to explore: