*Bubble sort is a popular sorting algorithm that compares the adjacent elements in a list and swaps them if they are not in the specified order.*

*This tutorial will explain how to implement the bubble sort algorithm in C++ using code examples.*

## Table of contents

## How Bubble Sort Works

The bubble sort algorithm, also known as sinking sort, is the most straightforward sorting algorithm. It goes through an array repeatedly, compares adjacent elements, and swaps them if they are out of order. We can use the bubble sort algorithm to sort in ascending (largest element last) or descending order (largest element first). Let’s look at an example of how the bubble sort algorithm can sort an array of five numbers in **ascending order**.

**First Iteration**

- Starting from the first element in the array, compare the first and second elements.
- Swap the elements if the first element is greater than the second element.
- Compare the second and third elements, and swap them if they are not in order.
- Proceed with the above process until the last element.

Let’s look at the first pass, which means the algorithm goes over the array:

The above image shows how the array looks after each step in the pass over the array. Note how the largest number in the array *bubbles* to the top of the array. Let’s look at the second pass:

The algorithm only swaps elements if the right element is less than the left element in the array. Finally, we have the third pass:

The number of passes over the array depends on its size and the arrangement of the array elements.

Below, you can see a visualization of how Bubble Sort works. Choose the length of your array in the box next to `Array Size (Max 30)`

then click `Generate Random Array`

to generate the numbers, then click `Start Sorting`

.

## Bubble Sort Pseudocode

Let’s look at the pseudo-code describing the bubble sort algorithm.

procedure bubbleSort(A : list of sortable items) n := length(A) for i := 0 to n-1 inclusive do for j := 0 to n-i-1 inclusive do // Element comparison if A[j] > A[j+1] then // If not in the correct order then swap the elements swap(A[j], A[j+1]) end if end for end for end procedure

## Optimized Bubble Sort in C++

Let’s look at the function to perform Bubble sort in C++.

#include <iostream> using namespace std; void optimizedbubbleSort(int arr[], int n) { int i, j; bool is_swapped; for (int i = 0; i < n-1; i++) { is_swapped=false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { is_swapped = true; int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } if (!is_swapped) { break; } } } void printArray(int arr[], int n){ for (int i = 0; i < n; i++){ cout << " " << arr[i]; } cout << "\n"; }

We introduce a variable is_swapped set it to False. We set is_swapped to True if we swap the elements after comparison. Otherwise, we leave it as False.

We use an if statement to check the value of is_swapped. If we get False, we break out of the loop, ensuring that we do not compare already sorted elements.

We have a function to print the array elements to the console called printArray().

Let’s look at the main function where we call the optimizedbubbleSort() function on an unsorted array of integers.

int main(){ int arr[] = {45, 32, 12, 22, 24, 11, 101}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Unsorted array:\n" << endl; printArray(arr, n); optimizedbubbleSort(arr, n); cout << "Sorted array:\n" << endl; printArray(arr, n); return 0; }

We use the `printArray()`

function to get the elements before and after sorting.

### How to Compile in C++

We can compile the code using the GNU C++ compiler g++. We can specify the name of the executable using the -o flag.

g++ -o bubble_sort.exe main.cpp ./bubble_sort.exe

Let’s run the code to see what happens:

Unsorted array: 45 32 12 22 24 11 101 Sorted array: 11 12 22 24 32 45 101

We successfully sort the array of numbers in ascending order.

## C++ Sorting Benchmark

### Sorting with 50,000 Elements Ten Times with C++

Let’s scale the application of the optimized Bubble Sort algorithm. We will define an array of 50,000 numbers and pass it to the Bubble sort algorithm, and we will repeat the sorting of the array ten times. Let’s look at the code:

#include <chrono> using namespace std::chrono; int main() { int n = 50 * 1000; int rerun = 10; int *arr = new int[n]; for (auto i = 0; i < n; i++) arr[i] = n - i; auto start = high_resolution_clock::now(); for (int r = 0; r < rerun; r++) { optimizedbubbleSort(arr, n); } auto stop = high_resolution_clock::now(); auto duration = duration_cast<seconds>(stop - start); cout << "Time taken by function to sort 50000 elements 10 times: " << duration.count() << " seconds" << endl; return 0; }

We use the high_resolution_clock::now() function from the chrono namespace to time the reruns of the function. Let’s compile and run the code to get the timing result:

Time taken by function to sort 50000 elements 10 times: 4 seconds

## Bubble Sort Complexity

### Time Complexity

Bubble sort employs two loops: an inner loop and an outer loop. The number of comparisons made is:

(n - 1 ) + (n - 2) + (n - 3) + ... + 1 = n(n-1)/2

Which approximates to $latex n^{2}$, therefore the complexity of the bubble sort algorithm is $latex O(n^{2})$.

#### Bubble Sort Worst Case Time Complexity

- Outer loop runs O(n) times
- As a result the worst-case time complexity of bubble sort is $latex O(n \times n) = O(n^{2})$.
- This is also the average case complexity, in other words, the elements of the array are in jumbled order and are neither ascending nor descending. This complexity occurs because irrespective of the arrangement of elements, the number of comparisons is the same.

#### Bubble Sort Best Case Time Complexity

- If the list is already sorted, outer loop runs O(n) times.

### Space Complexity

- Space complexity is O(1) because we use an extra variable temp for swapping.
- In the optimized bubble sort algorithm we use two extra variables temp and is_swapped. Therefore the space complexity is O(2).

### Summary

Congratulations on reading to the end of this tutorial! We went through how to do Bubble Sort with C++.

For further reading on the implementation of Bubble Sort, go to the articles:

For further reading on sorting algorithms in C++, go to the article How To Do Merge Sort in C++ where we will go through a performance test comparison between Merge and Bubble Sort.

Have fun and happy researching!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, heโs focused on bringing more fun and curiosity to the world of science and research online.