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

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

**What is Bubble Sort C++?**

__Bubble Sort__ 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**

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

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

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

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

**Pseudocode**

```
bubbleSort(int array[])
for i=0 ; i< end of array;i++
if array[i] > array[i+1]
swap array[i] and array[i+!]
end
```

In this code, we are iterating through the array, and if the current element is greater than the next element, we swap both of them.

**Brute Force Solution**

**Code in 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 C++**

**Code in 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 Complexity | O(n) |

Average Time Complexity | O( n2) |

Worst Time Complexity | O(n2) |

Space Complexity | O(1) |

**Worst Case Analysis for Bubble Sort**

The worst-case situation for Bubble Sort is one in which the algorithm works the hardest or requires the most comparisons and swaps. The worst-case situation for Bubble Sort is when the input array is arranged in reverse.

In the worst case, each of the n passes in Bubble Sort involves (n - 1) comparisons and swaps.

As a result, in the worst scenario, the total number of comparisons and swaps is roughly proportional to (n * (n - 1)) / 2, resulting in a quadratic time complexity of O(n^{2}).

So, when the input array is arranged in reverse, the worst-case scenario for Bubble Sort happens, resulting in a temporal complexity of O(n2) due to the quadratic number of comparisons and swaps necessary.

**Advantages of Bubble Sort 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 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 is the formula for bubble sort?**

Bubble Sort compares them and swaps them if two adjacent elements in an array are out of order . Until no more exchanges are required, this process is repeated. The method repeats this step for each element until the array is sorted.

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

**Which is the best sorting algorithm?**

The "best" sorting algorithm to use depends on the requirements and circumstances at hand. For general sorting tasks, QuickSort, MergeSort, and TimSort are frequently regarded as the finest algorithms, however the optimum algorithm depends on the dataset size and data distribution.

**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 **n **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 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 Python__, __Oops in python__, __Basics of C__, etc., along with some __Contests__ and __Interview Experiences__ only on __Coding Ninjas Studio__.

Do check out The __Interview Guide for Product Based Companies__ as well as some of the Popular Interview Problems from Top companies like __Amazon__, __Adobe__, __Google__, etc. on __Coding Ninjas Studio__.

Happy Learning!!