Introduction

Sorting is a fundamental operation in computer science, and various algorithms have been developed to efficiently organize data. One such algorithm is Bubble Sort. In this blog post, we will explore the Bubble Sort algorithm, provide its pseudocode, analyze its time and space complexity, and present a C++ implementation.

Bubble Sort Overview

Bubble Sort is a simple 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. The algorithm gets its name from the way smaller elements "bubble" to the top of the list.

Pseudocode for Bubble Sort

procedure bubbleSort(A: list of sortable items)
    n = length(A)
    for i from 0 to n-1
        for j from 0 to n-i-1
            if A[j] > A[j+1]
                swap(A[j], A[j+1])

Time Complexity

Bubble Sort has a time complexity of O(n^2) in the worst and average cases, where 'n' is the number of elements in the array. This is because, in the worst case, the algorithm needs to perform n iterations for each of the n elements. In the best-case scenario (when the array is already sorted), Bubble Sort has a time complexity of O(n).

Space Complexity

Bubble Sort is an in-place sorting algorithm, meaning it doesn't require additional memory to perform the sorting. Hence, its space complexity is O(1).

Implementation in C++

#include <iostream>

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

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], arr[j + 1]);
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Unsorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }

    bubbleSort(arr, n);

    std::cout << "\nSorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }

    return 0;
}

Conclusion

Bubble Sort, while straightforward, is not the most efficient sorting algorithm for large datasets. However, it serves as a good introduction to the concept of sorting algorithms. Understanding its simplicity and limitations can pave the way for exploring more advanced sorting techniques in the world of computer science.