Bubble sort is one of the simplest sorting algorithms that is based on swapping adjacent elements if they are present in the wrong order. It is a stable algorithm since it preserves the order of the original vector in case of repetition.
Bubble Sort C++ Algorithm Implementation
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
//program to sort the vector using bubble sort
void BubbleSort(vector<int> &nums){
int n = nums.size(), i, j;
for(i=0;i<n-1;i++){//we do not iterate through the last element since it is automatically sorted
for(j=0;j<n-1-i;j++){
if(nums[j]>nums[j+1])//elements are swapped if not found in increasing order
swap(nums[j], nums[j+1]);
}
}
return;
}
int main()
{
vector<int> nums;//initializing the vector
nums.push_back(5);
nums.push_back(2);
nums.push_back(10);
nums.push_back(3);
nums.push_back(8);
BubbleSort(nums);//calling the bubble sort function to sort the vector
int i;
for(i=0;i<nums.size();i++){
cout<<nums[i]<<" ";//printing the element of vector in a sorted manner
}
return 0;
}
Dry Run
Input: nums = [5, 2, 10, 3, 8]
First Pass (i=0)
//element in bold represents nums[j] and nums[j+1]
[5, 2, 10, 3, 8] => [2, 5, 10, 3, 8] //both the elements are compared and swapped since 5>2
[2, 5, 10, 3, 8] => [2, 5, 10, 3, 8] //the order will be unaltered in this iteration since 5<10
[2, 5, 10, 3, 8] => [2, 5, 3, 10, 8] //the elements will be swapped since 10>3
[2, 5, 3, 10, 8] => [2, 5, 3, 8, 10] //here you can see that last element is in its sorted position
Second Pass (i=1)
[2, 5, 3, 8, 10] => [2, 5, 3, 8, 10]
[2, 5, 3, 8, 10] => [2, 3, 5, 8, 10]//swapped since 5>3
[2, 3, 5, 8, 10] => [2, 3, 5, 8, 10]//after this we stop the iteration since the last 2 elements are already sorted
Now, the vector is already sorted but the algorithm doesn’t know if it is sorted. Hence, it will continue the iteration like before. The only difference is that there will be no swapping during the iteration.
Third Pass (i=2)
[2, 3, 5, 8, 10] => [2, 3, 5, 8, 10]
[2, 3, 5, 8, 10] => [2, 3, 5, 8,10]
Fourth Pass (i=3)
[2, 3, 5, 8,10] => [2, 3, 5, 8,10] //here the algorithm comes to an end
Time Complexity: O(N2)//in every case be it best or worst.
Optimized Implementation of Bubble Sort C++
In the previous algorithm, the iteration continues even if the vector is sorted. Because of this, the time complexity remains O(N2) even in the best case. In the optimized version, we try to avoid further iteration, if swapping doesn’t take place. Below we have shown the C++ implementation of bubble sort.
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
//program to sort the vector using bubble sort
void BubbleSort(vector<int> &nums){
int n = nums.size(), i, j;
bool exchange;
for(i=0;i<n-1;i++){//we do not iterate through the last element since it is automatically sorted
exchange = false;
for(j=0;j<n-1-i;j++){
if(nums[j]>nums[j+1]){//elements are swapped if not found in increasing order
swap(nums[j], nums[j+1]);
exchange = true;//if there elements are swapped then the algorithm doesn't stop
}
}
if(exchange==false)//in case there is no swapping in the inner loop, we break out of the loop
break;//this only happens if the vector is sorted
}
return;
}
int main()
{
vector<int> nums;//initializing the vector
nums.push_back(5);
nums.push_back(2);
nums.push_back(10);
nums.push_back(3);
nums.push_back(8);
BubbleSort(nums);//calling the bubble sort function to sort the vector
int i;
for(i=0;i<nums.size();i++){
cout<<nums[i]<<" ";//printing the element of vector in a sorted manner
}
return 0;
}
Best Case Time Complexity: O(N) //in case the vector is sorted
Worst Case Time Complexity: O(N2) //in case the vector is sorted in descending order
Space Complexity: O(1) //since the sorting is done in place
Hope you liked this article and if you want to explore more, do read Median of Two Sorted Arrays | Leetcode Problem #4. For more interesting articles, visit our website Codekyro.
1 thought on “Bubble Sort – A Stable Algorithm”