Bubble Sort | DSA in C++ - Software Development PDF Download

Introduction

Bubble Sort is a simple and commonly used sorting algorithm in computer science. It is named as such because smaller or larger elements "bubble" to the top or bottom of the list during each pass. Bubble Sort is easy to understand and implement, making it an excellent starting point for beginners in the field of Data Structures and Algorithms (DSA). In this article, we will explore the Bubble Sort algorithm in detail, providing multiple examples and simple code snippets to enhance your understanding.

Algorithm

The Bubble Sort algorithm works by repeatedly swapping adjacent elements if they are in the wrong order until the entire list is sorted. The basic steps of Bubble Sort are as follows:

• Start at the beginning of the list.
• Compare each pair of adjacent elements.
• If the elements are in the wrong order, swap them.
• Move to the next pair and repeat steps 2 and 3.
• Repeat steps 2 to 4 until no more swaps are needed (i.e., the list is sorted).

Let's now dive into some code examples to illustrate the Bubble Sort algorithm.

Example 1: Sorting an Array of Integers

#include <iostream>

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] and arr[j + 1]

                int temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

            }

        }

    }

}

int main() {

    int arr[] = {64, 34, 25, 12, 22, 11, 90};

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array before sorting: ";

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    bubbleSort(arr, n);

    cout << "\nArray after sorting: ";

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    return 0;

}

Output:

Array before sorting: 64 34 25 12 22 11 90

Array after sorting: 11 12 22 25 34 64 90

Explanation:
In the above code, we start with an array 'arr' containing unsorted integers. The 'bubbleSort' function is responsible for sorting the array using the Bubble Sort algorithm. It iterates over the array and compares each pair of adjacent elements. If an element is greater than the next element, it swaps them. This process is repeated until the array is fully sorted. Finally, we print the sorted array using the 'cout' statement.

Example 2: Sorting a String

#include <iostream>

#include <string>

using namespace std;

void bubbleSort(string& str) {

    int n = str.length();

    for (int i = 0; i < n - 1; i++) {

        for (int j = 0; j < n - i - 1; j++) {

            if (str[j] > str[j + 1]) {

                // Swap str[j] and str[j + 1]

                char temp = str[j];

                str[j] = str[j + 1];

                str[j + 1] = temp;

            }

        }

    }

}

int main() {

    string str = "openai";

        cout << "String before sorting: " << str << endl;

        bubbleSort(str);

        cout << "String after sorting: " << str << endl;

        return 0;

}

Output:

String before sorting: openai

String after sorting: aeinop

Explanation:

In this code example, we demonstrate how to use the Bubble Sort algorithm to sort a string. The 'bubbleSort' function takes a string 'str' as input and performs the sorting operation. It iterates over the characters of the string, comparing adjacent characters and swapping them if they are in the wrong order. The process continues until the entire string is sorted. Finally, we print the sorted string using the 'cout' statement.

Sample Problems

Problems 1: Implement the Bubble Sort algorithm to sort an array of floating-point numbers in descending order.

#include <iostream>

using namespace std;

void bubbleSort(float 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] and arr[j + 1]

                float temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

            }

        }

    }

}

int main() {

    float arr[] = {5.5, 3.3, 1.1, 4.4, 2.2};

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array before sorting: ";

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    bubbleSort(arr, n);

    cout << "\nArray after sorting: ";

    for (int i = 0; i < n; i++) {

        cout << arr[i] << " ";

    }

    return 0;

}

Problems 2: Write a program to sort a vector of strings using the Bubble Sort algorithm.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void bubbleSort(vector<string>& vec) {

    int n = vec.size();

    for (int i = 0; i < n - 1; i++) {

        for (int j = 0; j < n - i - 1; j++) {

            if (vec[j] > vec[j + 1]) {

                // Swap vec[j] and vec[j + 1]

                swap(vec[j], vec[j + 1]);

            }

        }

    }

}

int main() {

    vector<string> vec = {"apple", "orange", "banana", "grape"};

   

    cout << "Vector before sorting: ";

    for (const string& s : vec) {

        cout << s << " ";

    }

    bubbleSort(vec);

    cout << "\nVector after sorting: ";

    for (const string& s : vec) {

        cout << s << " ";

    }

    return 0;

}

Conclusion

In this article, we have explored the Bubble Sort algorithm in DSA using C++. We discussed the steps involved in the Bubble Sort algorithm and provided code examples for sorting arrays of integers and strings. We also included sample problems for further practice. Bubble Sort is a simple yet important sorting algorithm, and understanding its implementation will help you grasp fundamental concepts in DSA.