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.

__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

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

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