Bubble Sort Program in C++

Last Updated on August 25, 2023 by Mayank Dham

Sorting lies at the heart of countless computational tasks, from organizing data for efficient retrieval to optimizing search algorithms. Among the plethora of sorting techniques, the Bubble Sort algorithm stands as a simple yet instructive method to understand the fundamentals of sorting and algorithmic design. Written in Bubble Sort C++, showcases the core principles of comparing and swapping elements, making it an excellent starting point for those delving into the world of sorting algorithms.

In the realm of sorting, the Bubble Sort program in C++ offers a clear visualization of how smaller elements "bubble up" to their rightful positions within an array. Despite its modest efficiency compared to more advanced sorting algorithms, Bubble Sort is an essential learning tool. By grasping its inner workings, programmers not only gain insights into basic sorting concepts but also pave the way for comprehending more complex algorithms.

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).

Conclusion
The journey through the world of sorting algorithms has led us to the simple yet enlightening Bubble Sort algorithm. While not the most efficient sorting method for larger datasets, Bubble Sort shines as an educational tool that unveils the foundational concepts of sorting and the mechanics behind comparing and swapping elements. Through our exploration of Bubble Sort in C++, we’ve uncovered the step-by-step process of how elements "bubble up" to their sorted positions, providing valuable insights into algorithmic design and logic.

Understanding Bubble Sort goes beyond its basic implementation. It fosters an appreciation for the evolution of more advanced sorting algorithms, where efficiency and performance optimization become paramount. Moreover, the principles you’ve grasped from Bubble Sort will empower you to explore other sorting algorithms and their variations, enriching your programming skills and problem-solving capabilities.

FAQ Related to bubble sort program in C++

1. How does the Bubble Sort algorithm work?
Bubble Sort iterates through an array, comparing adjacent elements and swapping them if they’re out of order. This process is repeated until the entire array is sorted, with the largest (or smallest, depending on the sorting order) elements "bubbling up" to their proper positions.

2. Is Bubble Sort efficient for large datasets?
Bubble Sort has a worst-case time complexity of O(n^2), making it inefficient for larger datasets. It is generally outperformed by more advanced sorting algorithms like Quick Sort, Merge Sort, and Heap Sort.

3. What are the practical applications of Bubble Sort?
While Bubble Sort is not commonly used in practice due to its inefficiency, it can be useful for educational purposes and for sorting small arrays where simplicity is more important than performance.

4. How can I optimize Bubble Sort?
Bubble Sort can be optimized by incorporating a flag that tracks whether any swaps occurred during a pass. If no swaps are made in a pass, the array is already sorted, and the algorithm can terminate early.

5. Is Bubble Sort a stable sorting algorithm?
Yes, Bubble Sort is stable. It maintains the relative order of equal elements during the sorting process.

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++