Bubble sort in C++
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.
| Time Complexity | O(n2) |
| Best Case | O(n) |
| Worst Case | O(n2) |
| Space Complexity | O(1) |
| Avg. Comparisons | n(n-1)/2 |
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.
| 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
- Linearly Traverse array from left
- If the first item is greater than the 2nd item in the array, swap them.
- That is, arr[i] > arr[i+1], then swap
- Now, compare the next two elements.
- We will repeat all the previous steps until the given array is sorted.
An example can be seen below –
Example
As you can see in each pass we get the largest item pushed to rightmost position –
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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)
#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
Explanation
- The program demonstrates the bubble sort algorithm in C++.
- A swap function is used to interchange two array elements.
- The bubbleSort function repeatedly compares and swaps adjacent elements.
- After each pass, the largest element moves to its correct position at the end.
- The display function prints the array before and after sorting.
- The main function initializes the array and calls bubbleSort to sort it.
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 –
The above algorithm would have run all its iterations both the for loops would have implemented end to end
Arr = {10, 20, 30, 50, 60}
Even for this array which have got sorted in Pass1, we would have run all Passes all iterations.
Below code solves this using a flag variable
Method 2 (Optimization for already/nearly sorted)
#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
Explanation
- The program shows an optimized bubble sort in C++.
- The swap function exchanges two numbers.
- Bubble sort compares adjacent elements and swaps if needed.
- A swapped flag stops the algorithm early if the array is already sorted.
- The display function prints the array before and after sorting.
- The main function runs the sort on the array and shows results.
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
To Wrap It Up:
Bubble Sort is a simple and easy-to-implement sorting algorithm, suitable for small datasets. It helps in arranging elements in ascending or descending order, but its basic version is inefficient for large arrays due to a time complexity of O(n²).
Using a swapped flag or checking for nearly sorted arrays can optimize the algorithm by stopping unnecessary iterations. Despite its simplicity, for large datasets, more advanced sorting methods are recommended for better performance.
You can also learn similar sorting technique in C and Java.
FAQs
Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order. It continues until the array is fully sorted.
The worst and average-case time complexity is O(n²), while the best case (already sorted) is O(n). It is inefficient for large datasets.
Yes, Bubble Sort is stable because it preserves the relative order of equal elements. It is also in-place as it requires no extra memory.
Use Bubble Sort only for small or nearly sorted arrays. It’s easy to implement but not suitable for large datasets due to poor efficiency.
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.
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.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment
The algorithm can even be better if put a stopper to the iterations when the swapping stops.