Bubble Sort in C++ (Code with Example)

When a large amount of data is to be dealt with, the most efficient way is to store it in an optimized manner. As programmers often face lots of problems to solve on daily basis, it is quite easy to solve this problem in minimum time if your data is arranged in a specialized format, i.e. either ascending or descending format. Therefore, every programming language provides a class of algorithm known as Sorting which enables you to arrange your data in a specific format and sort them in ascending or descending manner.

There are many sorting techniques available, all with their own advantage and disadvantage, and can be used in different situations. In this article, we will study one such sorting algorithm i.e., bubble sort, and its algorithm. We will also learn the C++ code for sorting data using bubble sort and conclude with its applications. So, let's get started!

What is Bubble Sort?

The Bubble Sort, also called Sinking Sort, is a sorting algorithm that compares each pair of adjacent elements. Bubble sort is not an efficient sorting algorithm compared to others but it provides useful insights to beginners on what sorting algorithm is and how it works behind the scene. The basic technique of bubble sort is that the first element of the list is compared to the second, the second to the third element, and so on. Each iteration moves each element of the array closer to the end, similar to how air bubbles rise to the surface of the water. This is how bubble sort gets its name. Here, the sorting is done in the form of passes or iteration. As a result, the largest element is placed in its rightful place in the list at the end of each iteration. You can also say that the list's largest element rises to the top after the completion of each iteration/pass. 

Algorithm for Bubble Sort

Step1: for k = 0 to n-1 repeat Step 2

Step2: for j = k + 1 to n – k repeat

Step3: if A[j] > A[k]

             Swap A[j] and A[k]

             [end of inner for loop]

             [end if outer for loop]

Step4: end

How Does Bubble Sort Work?

1. If the order of adjacent elements is incorrect, we compare them ( a[k] > a[j] ) and swap them.
2. Assume we have an array of length 'n'. Therefore, to sort 'n' elements using the previous step, we require an 'n-1' pass. 
3. After following these steps, the largest element goes at the end of the array. The next largest is one place behind the last. The 'kth' largest element is swapped to its rightful place in the array in the 'kth' pass.
4. So basically, at least one element from 'n - k + 1' will appear at its right place at the end of the ith pass. It will be the 'kth' largest element (for 1 *= k *= n - 1) of the array. Because in the 'kth' pass of the array, in the 'jth' iteration (for 1 <= j <= n - k), we are checking if 'a[j] > a[j + 1]', and 'a[j]' will always be greater than 'a[j + 1]' when it is the largest element in range '[1, n - k + 1]'. We'll now swap it. The process will continue until the largest element in the array is at the '(n - k + 1)th' position.

 Pseudocode for Bubble Sort

begin bubbleSort(array):
      N <- length(array)
      for j = 0 to N:
    for i = 0 to N-1:
           if array[i] > array[i+1]
             temp <- array[i]
         array[i+1] <- array[i]
         array[i] <- temp
           end if
        end for
      end for
      return array
end bubbleSort
begin modifiedbubbleSort(array):
      N <- length(array)
      for j = 0 to N:
    flag = False
    for i = 0 to N-1:
           if array[i] > array[i+1]
             temp <- array[i]
         array[i+1] <- array[i]
         array[i] <- temp
         flag = True
           end if
        end for
    if flag == False:
       break
      end for
      return array
end modifiedbubbleSort

Here, we traverse the array using two iterative loops.

We begin with the '0th' element in the first loop, then we begin with an adjacent element in the second loop. We compare each of the neighboring components in the inner loop body and swap them if they are out of order. The heaviest element bubbles up at the end of each iteration of the outer loop.

Bubble Sort Example

Let us consider the below array of elements to sort.

As we can see from the above illustration, the greatest element bubbles up to the last with each pass, sorting the list. Each element is compared to its adjacent element and switched with one another if they are not in order.

If the array is to be sorted in ascending order at the end of the first pass, the largest element is placed at the end of the list. The second largest element is placed at the second last position in the list for the second pass, and so on.

At last, we will have sorted the entire list when n-1 (where n is the total number of entries in the list) passes. The final output of the bubble sort will be as shown below.

C++ Code for Bubble Sort 

#include<bits/stdc++.h>
#define swap(x,y) { x = x + y; y = x - y; x = x - y; }

using namespace std;

/**
    * Function to Sort the array using Modified Bubble Sort Algorithm
    * @param arr: Array to be Sorted
    * @param n: Size of array
    * @return : None
*/
void bubbleSort(int arr[], int n)
{
    int i, j;
    bool flag;
    // Outer pass
    for(i = 0; i < n; i++)
    {
        flag = false;                                   // Set flag as false
        for(j = 0; j < n-i-1; j++)
        {
            // Compare values
            if( arr[j] > arr[j+1])
            {
                swap(arr[j],arr[j+1]);
                flag = true;
            }
        }
        // If no to elements are swapped then
        // array is sorted. Hence Break the loop.
        if(!flag)
        {
            break;
        }
    }
}
int main(int argv, char* argc[])
{
    int arr[] = {1,5,6,8,3,4,7,2,9};
    int n = sizeof(arr)/sizeof(int);
    cout<<"Unsorted Array :";
    for(int i=0;i<n;i++)                            // Print the Original Array
        cout<<arr[i]<<" ";
    cout<<endl;
    bubbleSort(arr,n);                              // Call for Bubble Sort Function
    cout<<"Sorted Array :";
    for(int i=0;i<n;i++)                            // Print the Sorted Array
        cout<<arr[i]<<" ";
    return(0);
}

Output

Unsorted Array :1 5 6 8 3 4 7 2 9 
Sorted Array :1 2 3 4 5 6 7 8 9 

Time Complexity 

The time complexity of the bubble sort algorithm is O(n) for the best-case scenario when the array is completely sorted. Considering the average case and worst-case scenarios, the time complexity of bubble sort is O(n^2) where n is a total number of elements in the array. It is because we have to make use of two loops traversing through the entire array for sorting the elements. 

Applications

• Bubble sorts are used to teach students the foundations of sorting.
• Bubble sort is used when the complexity of the algorithm does not matter
• It is quite preferred by the programmers because of being short and simple

Conclusion

Sorting is one of the most used techniques by programmers to store and optimize a huge amount of data. By sorting the elements, You can provide a better visual to your data collection and reduce the time complexity of any program efficiently. In this article, we study one such sorting technique i.e. bubble sort which is the base to learn the sorting and its works. Bubble Sort is not commonly used compared to other sorting algorithms but still have its own importance in the technical world. Learning bubble sort is well worth the effort because it acts as a bridge to understanding higher-level concepts and makes it easier for you to understand more difficult topics.