Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Working of Bubble Sort Algorithm
2.1.
Iteration 1
2.2.
Iteration 2
2.3.
Iteration 3
3.
Implementation of Bubble Sort in C++
3.1.
C++
4.
Optimized Bubble Sort in C++
4.1.
Algorithm for Optimized Bubble Sort
4.2.
Implementation of Optimized Bubble Sort in C++ 
4.3.
C++
5.
Time and Space Complexities
6.
Characteristics of Bubble Sort
7.
Advantages of Bubble Sort in C++
8.
Disadvantages of Bubble Sort in C++
9.
Frequently Asked Questions
9.1.
What is the use of bubble sort?
9.2.
What are the five steps of the bubble sort algorithm?
9.3.
Why is it called bubble sort?
9.4.
Is bubble sort a stable algorithm?
9.5.
How many loops do we need for a bubble sort algorithm?
10.
Conclusion
Last Updated: May 10, 2024
Easy

Bubble Sort in C++

Author Avni Gupta
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Sorting is a fundamental concept in computer science and programming that involves arranging data collection in a specific order. The most common order for sorting data is numerical or alphabetical. we can use different sorting algorithms  to accomplish this.

Some of the algorithms are selection sort, merge sort, insertion sort, bubble sort, etc. 

Bubble Sort in C++

In this blog, we will focus on the sorting algorithm named bubble sort C++ and look at the different implementation methods as well.

Bubble Sort in C++ is an easy sorting algorithm that repeatedly iterates through the given list of elements, compares each adjacent element every time, and swaps them if they are not in order. 

This is a simple gist of how it works. Let us look at an example while explaining how it works stepwise for better understanding.

Working of Bubble Sort Algorithm

Let us take an example of an array that has the following elements - 6, 4, 8, 1, 5

working of bubble sort

Iteration 1

  • We iterate through the array.
     
  • We first compare the elements on the first and the second index.
     
  • Swap the elements if the element on the first index is greater than that on the second index.
     
  • Then we move on to the elements on the second and third indexes, compare them, and swap if the element on the second index is greater than the one on the third index.
     
  • Repeat this till the last element of the array.
iteration 1

Iteration 2

  • We repeat the same steps as iteration 1 till our array is sorted.
     
  • Notice that at the end of each iteration, the largest element present in the unsorted part of the array is finally placed at the end.

 

iteration 2

Iteration 3

  • Repeat the steps in iteration 1 till the last unsorted element.
     
  • For each iteration, we do the comparisons only until the last element is unsorted in the array.
     
iteration 3

The array is sorted when all the elements are placed at the right place

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation of Bubble Sort in C++

Now that we have understood how bubble sort works let's look at the various implementations of Bubble sort C++.

  • C++

C++

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
   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], arr[j+1]);
           }
       }
   }
}

void printArray(int arr[], int n) {
   for (int i = 0; i < n; i++) {
       cout << arr[i] << " ";
   }
   cout << endl;
}

int main() {

   int arr[] = {64, 34, 25, 12, 22, 11, 90};
   int n = sizeof(arr) / sizeof(arr[0]);

   cout << "Original array: ";
   printArray(arr, n);

   bubbleSort(arr, n);
   cout << "Array sorted using brute force bubble sort: ";
   printArray(arr, n);

   return 0;
}

Output

Original array: 64 34 25 12 22 11 90 
Array sorted using brute force bubble sort: 11 12 22 25 34 64 90 

 

Explanation

The bubbleSort() function implements the brute force version of the bubble sort algorithm. It takes an array arr and its size n as input and uses two nested loops to iterate over the array and compare adjacent elements. 

If two adjacent elements are in the wrong order, they are swapped. This process is repeated until the array is fully sorted. 

Time and Space Complexity

The time complexity of the brute force bubble sort is O(N2) because it must compare every pair of elements in the array. The Space complexity id O(1). because we are using only auxiliary variables.

Optimized Bubble Sort in C++

Optimized Bubble Sort in C++ enhances the traditional Bubble Sort algorithm's efficiency by minimizing unnecessary iterations. It includes a flag to track whether any swaps occurred during a pass. If no swaps are made, it concludes that the array is already sorted and terminates early. This optimization reduces the average-case time complexity to O(n) for nearly sorted arrays while maintaining O(n^2) in the worst-case scenario. By avoiding unnecessary comparisons, it significantly improves performance for partially sorted data sets.

Algorithm for Optimized Bubble Sort

  1. Start with an unsorted array of elements.
  2. Set a boolean flag swapped to true initially.
  3. Initialize a loop to iterate over the array, i from 0 to n-1, and continue looping while swapped is true.
  4. Within the loop, set swapped to false.
  5. Initialize another loop to iterate over the array from the first element to the second-to-last element, j from 0 to n-i-1.
  6. Within the inner loop, compare each adjacent pair of elements.
  7. If an element is greater than the next element, swap them and set swapped to true.
  8. After completing a pass through the array, if no swaps were made, the array is sorted, and the loop terminates.
  9. Otherwise, repeat steps 3-8 until the array is sorted.
  10. Print the sorted array.

Implementation of Optimized Bubble Sort in C++ 

  • C++

C++

#include <iostream>
using namespace std;

void optimizedBubbleSort(int arr[], int n) {
   bool swapped = true;
   for (int i = 0; i < n-1 && swapped; i++) {
       swapped = false;
       for (int j = 0; j < n-i-1; j++) {
           if (arr[j] > arr[j+1]) {
               swap(arr[j], arr[j+1]);
               swapped = true;
           }
       }
   }
}

void printArray(int arr[], int n) {
   for (int i = 0; i < n; i++) {
       cout << arr[i] << " ";
   }
   cout << endl;
}

int main() {

   int arr[] = {56, 99, -1, 4, 34, 9};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Original array: ";
   printArray(arr, n);

   optimizedBubbleSort(arr, n);
   cout << "Array sorted using optimized bubble sort: ";
   printArray(arr, n);

   return 0;
}

Output

Original array: 56 99 -1 4 34 9 
Array sorted using optimized bubble sort: -1 4 9 34 56 99 


Explanation

The optimizedBubbleSort() function implements an optimized version of the bubble sort algorithm. It takes an array arr and its size n as input and also uses two nested loops to iterate over the array and compare adjacent elements. 

However, it includes an additional optimization: if no swaps are made during a pass through the array, the algorithm knows that the array is already sorted and can exit early. 

Time and Space Complexity

The time complexity of the optimized force bubble sort is O(n) because it must compare every pair of elements in the array. The Space complexity is O(1). because we are using only auxiliary variables.

Time and Space Complexities

Name Complexity
Best Time ComplexityO(n)
Average Time ComplexityO( n2)
Worst Time ComplexityO(n2)
Space ComplexityO(1)

Characteristics of Bubble Sort

  • Simple Implementation: Bubble Sort is straightforward to implement, making it easy to understand and code, suitable for educational purposes and small datasets.
  • Comparison-Based: It relies on pairwise comparisons between adjacent elements to sort the array, comparing and swapping elements until the array is sorted.
  • Inefficient for Large Datasets: Bubble Sort's time complexity of O(n^2) makes it inefficient for large datasets, as it involves nested loops and multiple passes through the array.
  • Stable Sorting Algorithm: Bubble Sort preserves the relative order of equal elements, making it a stable sorting algorithm.
  • Space Complexity: Bubble Sort has a space complexity of O(1), as it sorts the array in place without requiring additional memory.
  • Adaptive Nature: While generally inefficient, Bubble Sort can be adaptive for nearly sorted arrays, requiring fewer iterations to complete sorting.

Advantages of Bubble Sort in C++

Programmers widely use bubble sort; let us look at its advantages.

  • The primary advantage of the bubble sort is that it is popular and easy to implement. 
     
  • In the bubble sort, elements are swapped in place without using additional temporary storage. 
     
  • The space requirement is at a minimum

Disadvantages of Bubble Sort in C++

Here are some disadvantages of using bubble sort as your sorting algorithm.

  • The main disadvantage of the bubble sort is that it does not deal well with a list containing a huge number of items. 
     
  • The bubble sort requires N2 processing steps for every N number of elements to be sorted. 
     
  • The bubble sort algorithm is unsuitable for real-life applications, only academic purposes.

 

 Also Read - Selection Sort in C

Frequently Asked Questions

What is the use of bubble sort?

A Bubble sort are used for typical small datasets and educational . It is frequently used for small or nearly sorted datasets, is easy to apply, and aids in the teaching of sorting ideas. However, in practical applications, it is incredibly inefficient for larger datasets.

What are the five steps of the bubble sort algorithm?

The Bubble Sort method compares nearby entries in an array, swaps them if they are out of order, and then repeats this procedure for every pair of elements from the start to the end of the array. This keeps happening until no further swaps are required.

Why is it called bubble sort?

Bubble Sort is named so because during each iteration, smaller or larger elements "bubble" to their correct positions, similar to bubbles rising to the surface in water. This sorting algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order, gradually moving larger elements towards the end of the array.

Is bubble sort a stable algorithm?

Yes, the bubble sort algorithm is stable. A stable sorting algorithm means that two elements with equal keys are in the same order in the sorted array as in the unsorted input array.

How many loops do we need for a bubble sort algorithm?

To sort an array containing elements, the bubble sort algorithm generally requires n-1 iterations of a loop to sort the array. In each iteration, the algorithm compares the adjacent elements and swaps them in case of wrong order.

Conclusion

In conclusion, we learned what Bubble Sort in C++ is and how it works. We looked at the two ways we can implement it - the Brute force and Optimized methods. We saw the time and space complexity as well.

Check these out:

Check out some of the amazing Guided Paths on topics such as Basics of PythonOops in pythonBasics of C, etc., along with some Contests and Interview Experiences only on Code360

Do check out The Interview Guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like AmazonAdobeGoogle, etc.
Happy Learning!!

Previous article
Binary Search Vs Ternary Search
Next article
Recursive Binary Search
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass