Bubble Sort In C++
There are various sorting algorithms that are required to sort a set of similar data (mostly array) in either increasing or decreasing order.
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. The algorithm is applied repeatedly until there is no more adjacent pair present in the wrong order.
This algorithm is a brute force algorithm so it is not efficient in the real world with large data sets as algorithms like merge sort, quicksort, heapsort performs asymptotically far better. Yet it is important to study this algorithm as it lays the foundation for the basics of the sorting algorithm.
If you preparing for a C++ interview, here's the resource to help you get started and ace the interview.
Example:
Let the given array be : {1,5,3,4,2}
After applying Bubble Sort to sort the array in Ascending order,
The array will be : {1,2,3,4,5}
Here is the stepwise array transformation:
First Pass:
{ 1, 5, 3, 4, 2} - { 1, 3, 5, 4, 2} - { 1, 3, 4, 5, 2} - { 1, 3, 4, 2, 5}
Second Pass:
{ 1, 3, 4, 2, 5} - { 1, 3, 2, 4, 5}
Third Pass :
{ 1, 3, 2, 4, 5} - { 1, 2, 3, 4, 5}
Fourth Pass:
{1, 2, 3, 4, 5} - No change as No element was in Incorrect order.
Bubble Sort Pseudocode:
We are given an input array with n elements which are supposed to be sorted in ascending order.
We start with the first element ( 0-based indexing ) and check if the element present at the ith index is greater than the (i+1)th element, then we swap the elements at index i and i+1.
If the above is not the case, then no swapping will take place.
Now “ i ” gets incremented and the above 2 steps happen again until the array is exhausted.
Now the largest element will be at the last index of the array.
Now we will again set i=0 and continue with the same steps that will eventually place second largest at second last place in the array. Now the last 2 indexes of the array are sorted.
In this way, we perform the steps (n-1) times repeatedly and the array becomes completely sorted.
Bubble Sort Code:
#include<bits/stdc++.h>
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]);
}
}
}
int main()
{
int n;
cout<<"Enter the Number of elements in array :"<<endl;
cin>>n;
int arr[n];
cout<<"Enter the array elements :"<<endl;
for(int i=0;i<n;i++)cin>>arr[i];
cout<<"\nOriginal array : ";
for(int i=0;i<n;i++)cout<<arr[i]<<' ';
cout<<endl;
BubbleSort(arr,n);
cout<<"\nArray after applying Bubble Sort : ";
for(int i=0;i<n;i++)cout<<arr[i]<<' ';
cout<<endl;
cout<<endl;
}
Output:
Enter the number of elements in array :
6
Enter the array element :
64 25 34 3 10
Original array : 64 25 34 21 3 10
Array after applying Bubble Sort : 3 10 21 25 34 64
Process returned 0 (0x0) execution time : 3.808 s
Press any key to continue.
Above Output Explanation:
The initial array is [ 64, 25, 34, 21, 3, 10 ]
First Pass ( i=0 ):
j=0 : arr[0]>arr[1] so we swap, and the array becomes : [ 25, 64, 34, 21, 3, 10 ]
j=1 : arr[1]>arr[2] so we swap, and the array becomes : [ 25, 34, 64, 21, 3, 10 ]
j=2 : arr[2]>arr[3] so we swap, and the array becomes : [ 25, 34, 21, 64, 3, 10 ]
j=3 : arr[3]>arr[4] so we swap, and the array becomes : [ 25, 34, 21, 3, 64, 10 ]
j=4 : arr[4]>arr[5] so we swap, and the array becomes : [ 25, 34, 21, 3, 10, 64 ]
Here, we can observe that the maximum element occupied the correct position.
In general, in (i)th pass I largest element occupies last I positions in the array when sorting in ascending order. That is why we need to only call the outer for loop (n-1) times instead of n times.
Second Pass ( i=1 ):
j=0 : arr[0]<arr[1] so no changes, array remains same : [ 25, 34, 21, 3, 10, 64 ]
j=1 : arr[1]>arr[2] so we swap, and the array becomes : [ 25, 21, 34, 3, 10, 64 ]
j=2 : arr[2]>arr[3] so we swap, and the array becomes : [ 25, 21, 3, 34, 10, 64 ]
j=3 : arr[3]>arr[4] so we swap, and the array becomes : [ 25, 21, 3, 10, 34, 64 ]
Third Pass ( i=2 ):
j=0 : arr[0]>arr[1] so we swap, and the array becomes :[ 21, 25, 3, 10, 34, 64 ]
j=1 : arr[1]>arr[2] so we swap, and the array becomes :[ 21, 3, 25, 10, 34, 64 ]
j=2 : arr[2]>arr[3] so we swap, and the array becomes : [ 21, 3, 10, 25, 34, 64 ]
Fourth Pass ( i=3 ):
j=0 : arr[0]>arr[1] so we swap, and the array becomes :[ 3, 21, 10, 25, 34, 64 ]
j=1 : arr[1]>arr[2] so we swap, and the array becomes :[ 3, 10, 21, 25, 34, 64 ]
Fifth Pass ( i=4 ):
j=0 : arr[0]<arr[1] so no changes, array remains same :[ 3, 10, 21, 25, 34, 64 ]
Hence, the array is now in Sorted Order.
Time Complexity Analysis:
Worst and Average Case Time Complexity: O(n*n). The worst case occurs when the array is reverse sorted.
Best Case Time Complexity: O(n). The best case occurs when the array is already sorted.
Auxiliary Space: O(1)
Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.
Sorting In Place: Yes
An algorithm is said to be in place if it does not need an extra space and produces an output in the same memory that contains the data by transforming the input ‘in-place’. However, a small constant extra space used for variables is allowed.
Stable: Yes
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
To achieve Best case Time Complexity we need to make a small change in the above code.
Currently, our code runs in the loop even if all elements are in the correct position. So we can change it by introducing a flag variable. If there are no swaps then the flag will be 0 after the loop and we can exit as no need to repeat the process again.
Here is the Updated Code with Optimisation:
#include<bits/stdc++.h>
using namespace std;
void BubbleSort(int arr[],int n)
{
for(int i=0;i<n-1;i++)
{
bool flag=0;
for(int j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
swap(arr[j],arr[j+1]);
flag=true;
}
}
if(flag==false)break;
}
}
int main()
{
int n;
cout<<"Enter the Number of elements in array :"<<endl;
cin>>n;
int arr[n];
cout<<"Enter the array elements :"<<endl;
for(int i=0;i<n;i++)cin>>arr[i];
cout<<"\nOriginal array : ";
for(int i=0;i<n;i++)cout<<arr[i]<<' ';
cout<<endl;
BubbleSort(arr,n);
cout<<"\nArray after applying Bubble Sort : ";
for(int i=0;i<n;i++)cout<<arr[i]<<' ';
cout<<endl;
cout<<endl;
}
When we enter a sorted array-like { 1, 2, 3, 4, 5} the outer loop runs only 1 time and the inner loop runs only N Times and thus Time Complexity comes down to O(N) from O(N*N).
Also, given an almost sorted array bubble sort can sort it in O(2*N) time complexity.
Advantages of Bubble Sort:
The built-in ability to detect whether the list is sorted efficiently is the only advantage of bubble sort over other sorting techniques.
When the list is already sorted (which is the best-case scenario), the complexity of bubble sort is only O(n).
It is faster than other sorting techniques in the case of sorted arrays and consumes less time to describe whether the input array is sorted or not.
Application:
Bubble sort can be used when:
Time Complexity is not an issue.
Short and easy Code is Required.
One of the real-life examples is to sort a group of students with respect to their heights where they compare themselves in pairs.
It is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to the x-axis), and with incrementing y, their order changes (two elements are swapped) only at intersections of two lines.
Conclusion:
Even though for large Data sets we cannot use this algorithm, but we simply cannot ignore this as well as this is the simplest algorithm we can describe to a Computer.
Also, this algorithm lays the building block for understanding other sorting algorithms like odd-even sorting, Cocktail Shaker sort, etc.