C++ Program For Bubble Sort Algorithm

Bubble Sort is a straightforward comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. In this article, you will learn how the Bubble Sort algorithm works, its implementation in C++, and an optimization technique.

Problem Statement

Efficiently organizing a collection of items is a fundamental task in computer science. For instance, when dealing with an array of numbers, arranging them in ascending or descending order is often necessary for further processing, analysis, or presentation. The challenge is to devise a systematic method to reorder these elements correctly.

Example

Consider an unsorted array of integers: [5, 1, 4, 2, 8]. After applying the Bubble Sort algorithm, the array will be sorted in ascending order: [1, 2, 4, 5, 8].

Background & Knowledge Prerequisites

To understand and implement Bubble Sort in C++, readers should be familiar with the following basic C++ concepts:

• Variables and Data Types: Understanding how to declare and use integer variables.
• Arrays: Knowledge of how to declare, initialize, and access elements in one-dimensional arrays.
• Loops: Proficiency with for loops for iterating through arrays.
• Conditional Statements: Understanding if statements for comparing elements.
• Functions: Basic concept of main function and custom functions (though not strictly necessary for a simple implementation).

Use Cases or Case Studies

While not the most efficient algorithm for large datasets, Bubble Sort has a few specific use cases where its simplicity might be preferred or its characteristics are relevant:

• Educational Purposes: It is often one of the first sorting algorithms taught due to its easy-to-understand logic, making it excellent for introducing sorting concepts.
• Small Data Sets: For arrays with a very small number of elements, the overhead of more complex algorithms might not be justified, and Bubble Sort performs adequately.
• Nearly Sorted Data: If an array is already mostly sorted, Bubble Sort can perform relatively well, especially the optimized version which can detect an already sorted array quickly.
• Simple Proof-of-Concept: In scenarios where a quick, simple sorting mechanism is needed without performance being a critical concern, Bubble Sort can be a convenient choice.
• Visualizations: Its step-by-step comparisons and swaps make it very intuitive to visualize, often used in demonstrations of sorting algorithms.

Solution Approaches

1. Basic Bubble Sort Algorithm

This approach involves iterating through the array multiple times, comparing adjacent elements and swapping them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position.

// Basic Bubble Sort Algorithm
#include <iostream>
#include <vector> // Using vector for dynamic arrays, but can also use fixed-size arrays
#include <algorithm> // For std::swap

void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    // Outer loop for passes
    for (int i = 0; i < n - 1; ++i) {
        // Inner loop for comparisons and swaps
        // (n-1-i) because the last 'i' elements are already in place
        for (int j = 0; j < n - 1 - i; ++j) {
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap them if they are in the wrong order
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> numbers = {5, 1, 4, 2, 8};

    std::cout << "Original array: ";
    printArray(numbers);

    bubbleSort(numbers);

    std::cout << "Sorted array (Basic Bubble Sort): ";
    printArray(numbers);

    return 0;
}

Run

Sample Output:

Original array: 5 1 4 2 8 
Sorted array (Basic Bubble Sort): 1 2 4 5 8

Stepwise Explanation:

1. Outer Loop (i): This loop controls the number of passes through the array. For an array of n elements, n-1 passes are sufficient because in each pass, at least one element (the largest unsorted one) is placed in its final sorted position.
2. Inner Loop (j): This loop iterates through the unsorted portion of the array. It starts from the first element (j=0) and goes up to n-1-i. The -i part is crucial because after i passes, the last i elements are already sorted and do not need to be compared again.
3. Comparison and Swap: Inside the inner loop, arr[j] is compared with its adjacent element arr[j+1]. If arr[j] is greater than arr[j+1] (for ascending order), they are swapped.
4. Bubbling Effect: With each iteration of the inner loop, the largest element among the compared pair "bubbles up" towards its correct position at the end of the unsorted segment.

2. Optimized Bubble Sort Algorithm

This version adds a simple optimization: if no swaps occur during a full pass through the array, it means the array is already sorted, and we can stop early. This significantly improves performance for nearly sorted or already sorted arrays.

// Optimized Bubble Sort Algorithm
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

void optimizedBubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped; // Flag to check if any swap occurred in a pass

    // Outer loop for passes
    for (int i = 0; i < n - 1; ++i) {
        swapped = false; // Reset flag for each pass
        // Inner loop for comparisons and swaps
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true; // A swap occurred
            }
        }

        // If no two elements were swapped by inner loop, then array is sorted
        if (!swapped) {
            break;
        }
    }
}

int main() {
    std::vector<int> numbers1 = {5, 1, 4, 2, 8};
    std::vector<int> numbers2 = {1, 2, 3, 4, 5}; // Already sorted array

    std::cout << "Original array 1: ";
    printArray(numbers1);
    optimizedBubbleSort(numbers1);
    std::cout << "Sorted array 1 (Optimized Bubble Sort): ";
    printArray(numbers1);

    std::cout << "\\nOriginal array 2: ";
    printArray(numbers2);
    optimizedBubbleSort(numbers2);
    std::cout << "Sorted array 2 (Optimized Bubble Sort): ";
    printArray(numbers2);

    return 0;
}

Run

Sample Output:

Original array 1: 5 1 4 2 8 
Sorted array 1 (Optimized Bubble Sort): 1 2 4 5 8 

Original array 2: 1 2 3 4 5 
Sorted array 2 (Optimized Bubble Sort): 1 2 3 4 5

Stepwise Explanation:

1. swapped Flag: A boolean variable swapped is introduced and initialized to false at the beginning of each pass (outer loop iteration).
2. Tracking Swaps: Inside the inner loop, whenever a swap occurs, swapped is set to true.
3. Early Exit Condition: After the inner loop completes a full pass, if swapped is still false, it means no elements were out of order and thus no swaps were needed. This indicates the array is fully sorted, and the break statement exits the outer loop prematurely.
4. Efficiency Gain: For an already sorted array, this optimization reduces the time complexity to O(n) in the best-case scenario (only one pass needed), compared to O(n^2) for the basic version which would perform all n-1 passes.

Conclusion

Bubble Sort is a foundational sorting algorithm, valued for its conceptual simplicity and ease of implementation. While its quadratic time complexity (O(n^2)) makes it inefficient for large datasets, it serves as an excellent starting point for understanding more complex sorting techniques. The optimized version offers a significant improvement for nearly sorted arrays by allowing for an early exit.

Summary

• Mechanism: Compares adjacent elements and swaps them if they are in the wrong order, repeatedly.
• Bubbling: Largest unsorted element "bubbles" to its correct position in each pass.
• Time Complexity:
• Worst-case/Average-case: O(n^2)
• Best-case (Optimized): O(n) (for already sorted arrays)
• Space Complexity: O(1) (in-place sorting).
• Stability: It is a stable sorting algorithm (maintains the relative order of equal elements).
• Use: Primarily for educational purposes, very small datasets, or when simplicity outweighs performance concerns.