Lecture Notes on Bubble Sort Algorithm

Introduction to Bubble Sort

Bubble Sort is a simple sorting algorithm.
Works by repeatedly swapping adjacent elements if they are in the wrong order.
Not suitable for large datasets due to high average and worst-case time complexity.

How Bubble Sort Works

Multiple Passes:
- In each pass, the largest unsorted element is moved to its correct position in a sorted array.
- After k passes, the largest k elements are in their correct positions.
Swapping Mechanism:
- Compare adjacent elements and swap if the first is greater than the second.
- Continue this process until no swaps are needed, indicating the list is sorted.

Code Implementation

C++

#include<bits/stdc++.h>
using namespace std;

// Optimized Bubble Sort
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
}

// Function to print a vector
void printVector(const vector<int>& arr) {
    for (int num : arr)
        cout << " " << num;
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    cout << "Sorted array: \n";
    printVector(arr);
    return 0;
}

Python

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

# Driver code
a = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(a)
print("Sorted array:", a)

Complexity Analysis

Time Complexity: O(n^2)
Auxiliary Space: O(1)

Advantages of Bubble Sort

Simple and easy to understand.
Does not require additional memory space.
Stable sort: maintains the order of equal elements.

Disadvantages of Bubble Sort

Inefficient for large datasets due to quadratic time complexity.
Limited practical applications, mostly educational.

Understanding the Bubble Sort Algorithm

Lecture Notes on Bubble Sort Algorithm

Introduction to Bubble Sort

How Bubble Sort Works

Code Implementation

C++

Python

Complexity Analysis

Advantages of Bubble Sort

Disadvantages of Bubble Sort

Additional Resources