Bubble Sort C++

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

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

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:

• Sorting in Data Structure
   
• Searching and Sorting Algorithms
   
• Counting Sort
   

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