Bubble Sort Program in C++ - [Algorithm with Explanation]

Today we will learn Bubble Sort Program in C++. So, before getting started you should have a basic knowledge about bubble sorting in C++.

Table of Contents

What is a Bubble Sort?

This is one of the simplest and most popular sorting methods. The basic idea is to pass through the elements sequentially several times (n-1) times. In each pass, we compare successive elements (x[i] with x[i+1]) and interchange the two if they are not in the required order.

One element is placed in its correct position in each pass. In the first pass, the largest element will sink to the bottom, second largest in the second pass and so on. Thus, a total of n-1 passes are required to sort ‘n’ keys.

For Example: 25 37 12 48 57 33

1st Pass:

2nd Pass :

3rd Pass :

4th Pass:

5th Pass:

Bubble Sort Algorithm:

1 Step: START.

2 Step: Pass=1.

3 Step: i=0.

4 Step: if x[i]>x(i+1) then interchange x[i] and x[i+1]

5 Step: i=i+1

6 Step: If i<=n-1-Pass then go to step 4

7 Step: Pass=Pass+1.

8 Step: If Pass<n then go to step 3.

9 Step: STOP.

The efficiency of Bubble Sort:

There are n-1 comparisons in the first pass,n-2 in the second pass and 1 in the n-1th pass.

Therefore Total number of comparisons = (n-1)+(n-2)+…+1=n(n-1)/2.

The same number of passes is required in the best case (already sorted) and the worst case (elements in the reverse order). Hence the Best case and worst-case time complexity is O(n^2).

Advantages:

It is Simple Sorting Method.

No additional Data Structure is required.

It is in-place sorting method.

It is a stable sorting method.

Disadvantages:

It is very inefficient method-O(n^2).

Even if the elements are in the sorted order, all n-1 passes will be done.

1. Bubble Sort Program in C++

In this program, we will enter the numbers randomly and these numbers are stored in the array. After entering the numbers the program will start executing and then after sorting the compiler will print sorted array on the screen.

//Learnprogramo - programming made simple
#include<iostream>
using namespace std;
int main()
{
	int number, i, a[100], j, temp;
	cout<<"Enter total number of elements :";
	cin>>number;
	cout<<"Enter "<<number<<" numbers :";
	for(i=0; i<number; i++)
	{
		cin>>a[i];
	}
	cout<<"Sorting array using bubble sort technique...\n";
	for(i=0; i<(number-1); i++)
	{
		for(j=0; j<(number-i-1); j++)
		{
			if(a[j]>a[j+1])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
	cout<<"Elements sorted successfully..!!\n";
	cout<<"Sorted list in ascending order :\n";
	for(i=0; i<number; i++)
	{
		cout<<a[i]<<" ";
	}
}

Output:

Explanation:

First For Loop: First Iteration-

Assume user gives input of 5 numbers.

for(i=0;0<4;0++) The Condition is TRUE so it will enter in the second for loop.

Second For Loop: First Iteration-

for(j=0;0<5-0-1;0++) The Condition is TRUE so the compiler will enter in the if statement.

if(a[0]>a[1])->if(8>7) It means condition is TRUE so temp=10.Now a[j]=a[j+1]->a[0]=a[1]->a[0]=7. And a[j+1]=temp->a[1]=8. So the array will become 7 8 4 5 9 and j will be incremented by 1.

Second For Loop: Second Iteration-

for(j=1;1<5-0-1;1++) the condition is TRUE so the compiler will enter into if statement if(8>4) it means the condition is TRUE.

So like this process continuously goes on.

Improving Efficiency of Bubble Sort:

It is quite possible that the array gets sorted before all n-1 passes are complete. To avoid unnecessary passes, we have to check whether the array has got sorted at the end of each pass.

This can be done by finding out if an interchange was made in a pass. If no interchanges were done, it implies that the array has got sorted. It can be checked by using a flag.

Bubble Sort Improving Efficiency Algorithm:

1 Step: START.

2 Step: Pass=1.

3 Step: swap=FALSE.

4 Step: i=0.

5 Step: If x[i]>x[i+1] then Interchange x[i] and x[i+1] and Swap=TRUE.

6 Step: i=i+1.

7 Step: If i<=n-Pass-1 then go to step 5.

8 Step: If swap=FALSE then go to step 11.

9 Step: Pass=Pass+1.

10 Step: If Pass<n then go to step 3.

11 Step: STOP.

2. Improved Bubble Sort Program in C++

//Learnprogramo - programming made simple
#include<iostream>
using namespace std;
int main()
{
    int n;
    cout<<"Enter number of element you want to store: ";
    cin>>n;
    int arr[n],i,j;
    cout<<"Enter array values:\n";
    //taking the array value 
    //from user
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    //here this flag will help
    //to optimise the solution
    //first initialise flag=1
    int flag=1;
    //Now we will sort the array
    //if my flag value is 1 then only 
    //the loop will execute
    for(i=0;i<n-1 && flag==1;i++)
    {
        //here after each time of j loop
        // we will re-initialize the flag to 0
        flag=0;
        for(j=0;j<n-i-1;j++)
        {
            //checking if previous value is
            //grater than next one or not
            if(arr[j]>arr[j+1])
            {
                //temp will temporarly store
                //the value of arr[j]
                //then we will swap the values
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                //Here if there is a swap then
                // we will make it 1
                flag=1;
            }
        }
    }
    cout<<"After Bubble sort the array is:\n";
    for(i=0;i<n;i++)
    cout<<arr[i]<<" ";
    return 0;
}

Output: