Bubble sort in C++

March 18, 2022

What is Bubble Sort in C++?

Bubble Sort in C++, is one of the popular sorting techniques, that we use in data structures. The logical arranging of data is known as sorting.  Using the algorithm of bubble sort we can sort any linear data structure.

  • The logical sorting order can be ascending or descending.
  • This is a simple sorting algorithm but it is not the best. 
bubble C++
Time Complexity O(n2)
Best Case O(n)
Worst Case O(n2)
Space Complexity O(1)
Avg. Comparisons n(n-1)/2

Steps to implement bubble sort

  1. Linearly Traverse array from left
  2. If the first item is greater than the 2nd item in the array, swap them.
    1. That is, arr[i] > arr[i+1], then swap 
  3. Now, compare the next two elements.
  4. We will repeat all the previous steps until the given array is sorted.

An example can be seen below –

Bubble Sort in C++

Example

As you can see in each pass we get the largest item pushed to rightmost position –

Bubble Sort in C++

Methods discussed

  • Method 1: Usual bubble sort
  • Method 2: Optimization for already/nearly sorted array

Algorithm for Bubble Sort in C++

  • Step1: Repeat step 1 to 4 for i=0 to n
  • Step2: For j=0 to n
  • Step3: if(arr[j]>arr[j+1]
  • Step4: swap(arr[j],arr[j+1])
  • Step5: End

C++ program for bubble sort (Method 1)

Run 
#include <iostream>
using namespace std;

void swap(int *var1, int *var2)
{
    int temp = *var1;
    *var1 = *var2;
    *var2 = temp;
}
//Here we will implement bubbleSort.
void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)
       //Since, after each iteration rightmost i elements are sorted.
       for (j = 0; j < n-i-1; j++) 
           if (arr[j] > arr[j+1])
               swap(&arr[j], &arr[j+1]);
}
// Function to print array.
void display(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        cout << arr[i] << "\t";
        
    cout<<endl;
}
//Main function to run the program.
int main()
{
    int array[] = {5, 3, 1, 9, 8, 2, 4,7};
    int size = sizeof(array)/sizeof(array[0]);
    
    cout<<"Before bubble sort: \n";
    display(array, size);//Calling display function to print unsorted array.
    
    bubbleSort(array, size);
    
    cout<<"After bubble sort: \n";
    display(array, size);//Calling display function to print sorted array.
    
    return 0;
}

Output

Before bubble sort: 
5 3 1 9 8 2 4 7 
After bubble sort: 
1 2 3 4 5 7 8 9

Method 2 (Bubble Sort)

There is an issue with the above method that even if the array is already sorted or nearly sorted. The algorithm will run its whole iterations.

We can stop all further iterations if the array becomes sorted and not continue with the rest of the iteration.

Below code demonstrates that –

Method 2 (Optimization for already/nearly sorted)

Run 
#include <iostream>
using namespace std;

void swap(int *var1, int *var2)
{
    int temp = *var1;
    *var1 = *var2;
    *var2 = temp;
}

// Here we will implement bubbleSort.
void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)
   {
        // for optimization when array is already sorted & no swapping happens
       bool swapped = false;
       
       //Since, after each iteration rightmost i elements are sorted.
       for (j = 0; j < n-i-1; j++) 
       { 
           if (arr[j] > arr[j+1]){
                swap(&arr[j], &arr[j+1]);
                // swapping happenned so change to true
                swapped = true;
           }
       }
       // if no swaps happenned in any of the iteration
       // array has become sorted so stop with the passes
       if(swapped == false)
            break;
   }
}

// Function to print array.
void display(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
}

//Main function to run the program.
int main()
{
    int array[] = {10, 20, 30, 40, 50};
    int size = sizeof(array)/sizeof(array[0]);
    
    cout<<"Before bubble sort: \n";
    display(array, size);//Calling display function to print unsorted array.
    
    bubbleSort(array, size);
    
    cout<<"After bubble sort: \n";
    display(array, size);//Calling display function to print sorted array.
    
    return 0;
}

Output

Before bubble sort: 
10 20 30 40 50 
After bubble sort: 
10 20 30 40 50
Bubble sort in C++

Advantages of using Bubble Sort

Using this as our sorting algorithm can help us in following ways:-

  • Requires less memory then other sorting techniques.
  • Easy to code.

Why Bubble sort Sucks !!!

  • Slow like a snail, time complexity is O(n2)
  • With large number it sucks even more as it becomes even more slow thanks to O(n2)
  • The algorithm will be slowest when the array is sorted by in reverse
  • Best Case : O(n), when its already sorted

You can also learn similar sorting technique in C and Java.

Time Complexity
For Bubble Sort in C++

Best

O(n)

Average

O(n2)

Worst

O(n2)

Space Complexity

O(1)

Quiz time

Fun Fact

The term Bubble Sort was coined in 1962, by Iverson  because, same as like bubbles the smaller or lighter elements comes up (at start) and bigger or heavier elements goes down (at end). Before that, bubble sort was referred as “Sorting by exchange”, and after that it was re-ferred as “Exchange sorting”

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting

One comment on “Bubble sort in C++”


  • Nishant

    The algorithm can even be better if put a stopper to the iterations when the swapping stops.