Bubble Sort – A Stable Algorithm

Bubble Sort Algorithm

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”

  1. Pingback: Selection Sort Algorithm - CodeKyro

Leave a Reply

Your email address will not be published. Required fields are marked *