C++ Program for Bubble Sort (Optimized)

Hello Everyone!

In this tutorial, we will learn how to implement the optimized version of the Bubble Sort Algorithm, in the C++ programming language.

To understand the Bubble Sort Algorithm from scratch, we will highly recommend you to first visit our tutorial on the same, as we have covered it's step-by-step implementation, here: https://www.studytonight.com/data-structures/bubble-sort

Code:

#include <iostream>

#include<vector>

using namespace std;

//Global variable declaration so that the variables can be used/accessed within any of the methods
int n;
//Separate method to print the list provided by the calling method
void printElems(vector < int > list) {
    int i;
    for (i = 0; i < n; i++)
        cout << list[i] << "  ";

}

//The Optimized Bubble sort logic
void bubbleSort(vector < int > & a) {
    int i, j, k, swap, flag;
    int len = a.size();

    for (int i = len; i > 0; i--) {

        //initializing flag to 0 after each pass to check if swapping happens or not in a particular pass
        flag = 0;

        //Any number of variables can be used within the loop provided the syntax is correct.
        for (j = 0, k = 1; k < i; j++, k++) {
            if (a[j] > a[k]) {
                //Swap the elements as they are in opposite order
                swap = a[j];
                a[j] = a[k];
                a[k] = swap;

                // if swapping happens update flag to 1
                flag = 1;
            }

        }

        cout << "\n\nThe elements of the list after Pass " << n - i + 1 << " are  : ";
        printElems(a);

        if (flag == 0) {
            cout << "\n\nTerminating in the " << n - i + 1 << " pass out of " << n << " passes due to the optimized logic\n\n" << endl;
            break;
        }

    }

}

int main() {
    int i, num;

    //Declaring the Vector to store the integer elements to be sorted
    vector < int > v;

    cout << "\n\nWelcome to Studytonight :-)\n\n\n";
    cout << " =====  Program to implement the Optimized Bubble sort algo using Vectors, in CPP  ===== \n\n";

    //taking input from the command line (user)
    cout << " Enter the number of integers you want to sort : ";
    cin >> n;
    cout << "\n\n";

    for (i = 0; i < n; i++) {
        cout << "Enter number" << i + 1 << " :  ";
        cin >> num;
        v.push_back(num);

    }

    cout << "\n\nThe elements of the list before applying the Optimized Bubble sort algorithm are : ";

    //Calling the method to print the actual list
    printElems(v);

    //Calling the bubble sort algorithm
    bubbleSort(v);

    cout << "\n\nThe elements of the list after applying the Optimized Bubble sort algorithm are  : ";

    //Calling the method to print the sorted list
    printElems(v);

    cout << "\n\n\n";

    return 0;
}

Output 1: This scenario will explain to you the need for having an optimized Bubble Sort Algo, that can terminate the program if the list gets sorted in between rather than executing it over and over again till the end.

In above example, the list gets sorted after the very first pass itself, so in the 2nd pass, there is no swapping and hence our optimized algo understands that the list has already got sorted and terminates the program on this pass itself rather than making it to execute till the last pass.

For better understanding, you may refer to one of our tutorials here: https://www.studytonight.com/data-structures/bubble-sort

For any query, feel free to ask in the comments section down below!

Keep Learning : )