Bubble Sort Program in C++

In this article, we will learn about bubble sort, how to implement bubble sort program in C++.

What is Bubble Sort in C++

Bubble sort algorithm is used to sort the array in ascending order. The working of this algorithm and implementation of this algorithm is simplest to understand. Hence if you are a beginner, you will be able to grasp this algorithm easily.

This algorithm is called bubble sort algorithm because the movement of elements of the array is similar to the movement of air bubble in the water towards the surface of the water. Similarly when we apply bubble sort algorithm, lighter elements (elements with less values) move to the left end of the array.

In Bubble Sort Algorithm we swap the adjacent elements repeatedly till the elements are in the desired order. In ith iteration, we put ith smallest value to its correct index which is ith index by swapping the adjacent elements.

Bubble Sort surely is the simplest sorting algorithm to implement and to understand, but it’s not recommended because of its poor time complexity which is of O(NXN), where N is the number of elements in the array. There are more efficient algorithms available for sorting the array such as Merge Sort, Heap Sort, Quick Sort. These algorithms have the time complexity of O(NlogN).

Algorithm for Bubble Sort C++

We will run two nested loops in this algorithm, in the outer loop iterator i will iterate from 0 to N-1 and inner loop iterator j will iterate from 0 to N-i-1.
In the inner loop, check every step if a[j] is greater than a[j+1], if yes then swap the elements of index j and j+1, if not keep iterating j.

// implementation of Bubble Sort Algorithm in C++
// Bubble Sort C++
#include <bits/stdc++.h>
using namespace std;

// Function of implement bubble sort C++
void bubbleSort(vector<int> &v, int n)
{
    int i, j;
    for (i = 0; i < n - 1; i++)

   	 // Last i elements are already
   	 // in place
   	 for (j = 0; j < n - i - 1; j++)
   		 if (v[j] > v[j + 1])
   			 swap(v[j], v[j + 1]);
}

// Function to print an array
void printArray(vector<int> &v, int n)
{
    int i;
    for (i = 0; i < n; i++)
   	 cout << v[i] << " ";
    cout << endl;
}

// Driver code For Bubble Sort Program in C++
int main()
{
    int n;
  cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++){
  	 cin>>v[i];
  }
    bubbleSort(v, n);
    cout << "Sorted array: \n";
    printArray(v, n);
    return 0;
}

Dry Run of the Implementation of Bubble Sort Program in C++

Let us consider [3, 32, 26, 25, 35, 10] is the given array, we have to sort using bubble sort algorithm implementation.

First Pass (i=0)

j=0
[13, 32, 26, 25, 35, 10]
Here, a[j] < a[j+1], so no swap
j=1
[13, 32, 26, 25, 35, 10]
a[j]>a[j+1], so swap the elements.
[13, 26, 32, 25, 35, 10]
j=2
[13, 26, 32, 25, 35, 10]
a[j]>a[j+1], so swap the elements.
[13, 26, 25, 32, 35, 10]
j=3
[13, 26, 25, 32, 35, 10]
Here, a[j]< a[j+1], so no swap
j=4
[13, 26, 25, 32, 35, 10]
a[j]>a[j+1], so swap the elements.
[13, 26, 25, 32, 10, 35]

Second Pass (i=1)

j=0
[13, 26, 25, 32, 10, 35]
Here, a[j]< a[j+1], so no swap
j=1
[13, 26, 25, 32, 10, 35]
a[j]>a[j+1], so swap the elements.
[13, 25, 26, 32, 10, 35]
j=2
[13, 25, 26, 32, 10, 35]
a[j]>a[j+1], so swap the elements.
[13, 25, 26, 10, 32, 35]
j=3
[13, 25, 26, 10, 32, 35]
Here, a[j]< a[j+1], so no swap

Third Pass (i=2)

j=0
[13, 25, 26, 10 ,32, 35]
Here, a[j]< a[j+1], so no swap
j=1
[13, 25, 26, 10, 32, 35]
Here, a[j]< a[j+1], so no swap
j=2
[13, 25, 26, 10, 32, 35]
a[j]>a[j+1], so swap the elements.
[13, 25, 10, 26, 32, 35]

Fourth Pass (i=3)

j=0
[13, 25, 10, 26, 32, 35]
Here, a[j]< a[j+1], so no swap
j=1
[13, 25, 10, 26, 32, 35]
a[j]>a[j+1], so swap the elements.
[13, 10, 25, 26, 32, 35]
Here, we have achieved the sorted array.

Time Complexity for Bubble Sort C++

Case	Time Complexity
Best Case	O(N)
Average Case	O(NXN)
Worst Case	O(NXN)

Best Case Time Complexity for Bubble Sort C++

In the best case situation the array is already sorted. The Time Complexity becomes O(N).

Average Case Time Complexity for Bubble Sort C++

In this case, the elements in the array are jumbled( not in any kind of sorted order), then the time complexity will become O(NXN).

Worst Case Time Complexity for Bubble Sort Program in C++

In this case, the elements in the array are sorted in descending order. We have to make the most number of swaps operations in this case and then the time complexity will become O(NXN).

Space Complexity of Bubble Sort Algorithm

This Bubble Sort implementation in C++ only require one variable for swapping as extra space, so its Space Complexity will become O(1).

Other C++ Programs

C++ Program to Add Two Numbers
C++ Program to Reverse a Number
C++ program for heap sort

Bubble Sort in C++ with Program Code and Example

What is Bubble Sort in C++

Algorithm for Bubble Sort C++