AppDividend
Latest Code Tutorials

Bubble Sort In C++ Tutorial With Example | C++ Bubble Sort Program

0

Bubble Sort In C++ Tutorial With Example | C++ Bubble Sort Program is today’s topic. Bubble Sort is a sorting technique to sort an array, or we can say to sort a list of many numbers. This sorting algorithm is also known as Sinking Sort. Although this is the simplest method to sort the list of numbers, it is not the best way. We will discuss later it.

How does it work?

In this sorting method, each element is being compared with other elements of the list, and each time the largest, then the second largest, then 3rd largest number is placed at its correct position and so on until all the numbers are sorted. We will see one example of how it works?

Example:

Suppose we are given a list of number: 15 5 23 2 17. Now, we will apply bubble sort in this example and will see how it works:

If we consider these numbers in an array, the array will be:

0 1 2 3 4 Location
15 5 23 2 17 Array Value

 

So, when we will apply bubble sort here, we will see how the array will change in each step.

First Pass:

[15, 5 ,23 ,2 ,17] ———-> [5, 15, 23, 2 ,17]

[5, 15, 23, 2, 17] ———-> [5, 15, 23, 2, 17]

[5, 15, 23, 2, 17] ———-> [5, 15, 2, 23, 17]

[5, 15, 2, 23, 17] ———-> [5, 15, 2, 17, 23]

So, as said above, after every pass, the largest number will be placed at its correct place. Here, if you notice, you can see that a number is being compared with its adjacent number, if that number is larger than the next number (adjacent number), then they are being swapped. Like, here we 1st compared between 15 and 5, as 15 is more significant than 5 so we have swapped them. Similarly, at the last step, 17 and 23 are compared, and then we have swapped them. So, the array finally became.

Location 0 1 2 3 4
Array Value 5 15 2 17 23

 

Okay, now we will see the next passes:

Second Pass:

[5, 15, 2, 17, 23] —————-> [5, 15, 2, 17, 23]

[5, 15, 2, 17, 23] —————-> [5, 2, 15, 17, 23]

[5, 2, 15, 17, 23] —————-> [5, 2, 15, 17, 23]

[5, 2, 15, 17, 23] —————-> [5, 2, 15, 17, 23]

So, after the second pass, we can see that only 2 is swapped with 15. Rest all are at its the correct position, although the pass was continued until it reached to the last number.

Now, after Second Pass the array is:

Location 0 1 2 3 4
Array Value 5 2 15 17 23

 

Third Pass:

[5, 2, 15, 17, 23] ——————> [2, 5, 15, 17, 23]

[2, 5, 15, 17, 23] ——————> [2, 5, 15, 17, 23]

[2, 5, 15, 17, 23] ——————-> [2, 5, 15, 17, 23]

[2, 5, 15, 17, 23] ——————-> [2, 5, 15, 17, 23]

Now, you might be thinking that why I continued the steps after getting the sorted list? The answer is, we have two nested loops, so we have to continue the loop until the loop reaches to its end point, no matter whether you got your sorted list or not.

Similarly, the Fourth Pass will also be executed without any reason:). But I am not going to show you that, as it’s going to be boring.

Instead, we will see its algorithm.

Algorithm for Bubble Sort in C++

Step1: Take the input of N numbers as an array arr

Step2: Repeat step 2 to 5 For(i=0;i<n;i++)

Step3: For(j=0;j<n-i-1;j++)

Step4: if(arr[j]>arr[j+1]

Step5: swap(arr[j],arr[j+1])

Step6: End

Analysis:

In general, as we have N numbers, so we have to do

(N-1)+(N-2)+(N-3)+…+2+1 = ((N-1)*N)/2 comparisons.

So, the complexity of the algorithm is O(n^2)

This is for the worst case and average case

The complexity for Best Case is O(n)

Program of Bubble Sort in C++

#include<bits/stdc++.h>
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];
	}
	//Now we will sort the array
	for(i=0;i<n-1;i++)
	{
		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;
			}
		}
	}
	cout<<"After Bubble sort the array is:\n";
	for(i=0;i<n;i++)
	cout<<arr[i]<<" ";
	return 0;
}

The output is above the program is following.

 

Bubble Sort Program in C++

Okay, now you might be thinking that cannot we optimize this program so that loop gets over when we encounter a sorted list?

My answer is YES; we can. For this, please refer to the given program:

Optimize solution of Bubble Sort:

Below is the optimized program.

#include<bits/stdc++.h>
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;
}

The output of the above program is following.

C++ Bubble Sort Program Tutorial With Example

 

Finally, Bubble Sort In C++ Tutorial With Example | C++ Bubble Sort Program is over.

Leave A Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.