Lecture 332:- Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Algorithm:

1. Start from the first element (index 0) and compare it with the next element (index 1).
2. If the first element is greater than the second element, swap them.
3. Move to the next pair of elements (index 1 and index 2) and repeat the comparison and swap if needed.
4. Continue this process until the last pair of elements (index n-1 and index n) is reached.
5. At the end of the first pass, the largest element will be at its correct position at the end of the array.
6. Repeat steps 1 to 5 for n-1 passes (n is the number of elements in the array).
7. After each pass, the last i elements are already sorted, so they don't need to be considered in the subsequent passes.

Here's the C++ implementation of the Bubble Sort algorithm:

cppCopy code

#include <iostream> #include <vector> using namespace std; void bubbleSort(vector<int>& arr) {    int n = arr.size();    bool swapped;    for (int i = 0; i < n - 1; i++) {        swapped = false;        // Compare adjacent elements and swap if needed        for (int j = 0; j < n - i - 1; j++) {            if (arr[j] > arr[j + 1]) {                swap(arr[j], arr[j + 1]);                swapped = true;            }        }        // If no two elements were swapped in the inner loop, the array is already sorted        if (!swapped) {            break;        }    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};    cout << "Original Array: ";    display(arr);    bubbleSort(arr);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the bubbleSort function sorts the input vector using the Bubble Sort algorithm. The outer loop runs for n-1 passes, and the inner loop compares adjacent elements and swaps them if needed. The swapped variable is used to optimize the algorithm by checking if any swaps were made in the inner loop. If no swaps were made, the array is already sorted, and the algorithm breaks out of the loop early.