C++ Program For Bubble Sort Using Array

Sorting data is a fundamental operation in computer science, essential for efficient data retrieval and processing. In this article, you will learn how to implement the Bubble Sort algorithm using arrays in C++, a classic method for organizing numerical data.

Problem Statement

The challenge is to arrange a given sequence of elements in an array into a specific order, typically ascending or descending. An unsorted array can make tasks like searching for a specific value inefficient, highlighting the need for effective sorting algorithms.

Example

Consider an unsorted array of numbers: [64, 34, 25, 12, 22, 11, 90]. After applying a sorting algorithm, the array should become: [11, 12, 22, 25, 34, 64, 90].

Background & Knowledge Prerequisites

To understand and implement Bubble Sort in C++, familiarity with the following concepts is helpful:

• C++ Basics: Understanding variables, data types, and basic input/output operations.
• Arrays: Knowledge of how to declare, initialize, and access elements in one-dimensional arrays.
• Loops: Proficiency with for loops for iterating through arrays and controlling program flow.
• Conditional Statements: Understanding if statements for comparing elements.
• Swapping: The concept of exchanging the values of two variables.
• Comparison-based Sorting: A general idea that sorting algorithms often work by comparing elements.

Use Cases

Bubble Sort, while not the most efficient for large datasets, has its place and illustrates fundamental sorting principles. Here are a few practical scenarios:

• Educational Tool: It's an excellent algorithm for beginners to understand how sorting works due to its straightforward logic.
• Small Datasets: For very small arrays (e.g., fewer than 10-20 elements), its simplicity might outweigh the performance difference compared to more complex algorithms.
• Nearly Sorted Data: If an array is already mostly sorted, Bubble Sort can perform relatively quickly in its optimized form, as fewer passes are needed.
• Interactive Visualizations: Its step-by-step swapping makes it easy to visualize and demonstrate sorting in educational software.
• Testing Other Algorithms: Sometimes used as a baseline to compare the performance of more advanced sorting algorithms on small inputs.

Solution Approaches

Bubble Sort Algorithm

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, indicating the list is sorted. Larger elements "bubble up" to the end of the array with each pass.

// Bubble Sort using Array
#include <iostream>
#include <vector>    // Using vector for flexibility, dynamic array behavior
#include <algorithm> // For std::swap

// Function to print the array elements
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Initialize an unsorted array (using std::vector as a dynamic array)
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    int n = arr.size();

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

    // Step 2: Implement Bubble Sort algorithm
    // Outer loop controls the number of passes
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false; // Flag to optimize: if no swaps in a pass, array is sorted
        // Inner loop for comparisons and swaps within each pass
        // The last 'i' elements are already in place, so we don't need to check them
        for (int j = 0; j < n - 1 - i; ++j) {
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                // Swap if elements are in the wrong order (for ascending sort)
                std::swap(arr[j], arr[j + 1]);
                swapped = true; // Mark that a swap occurred
            }
        }
        // If no two elements were swapped by inner loop, then the array is sorted
        if (!swapped) {
            break;
        }
    }

    // Step 3: Print the sorted array
    std::cout << "Sorted array:   ";
    printArray(arr);

    return 0;
}

Run

Sample output from the above C++ program:

Original array: 64 34 25 12 22 11 90 
Sorted array:   11 12 22 25 34 64 90

Stepwise Explanation:

1. Initialization: An integer std::vector named arr is declared and initialized with unsorted values. n stores the number of elements. A helper function printArray displays the array contents.
2. Outer Loop (i): This loop iterates n-1 times, representing the maximum number of passes needed. In each pass, at least one element "bubbles up" to its correct sorted position at the end of the unsorted portion of the array.
3. Inner Loop (j): This loop performs comparisons and potential swaps for adjacent elements. It runs from the beginning up to n - 1 - i. The - i optimization is crucial because after each full pass i, the largest i elements are already correctly positioned at the end of the array, so they don't need to be checked again.
4. Comparison and Swap: Inside the inner loop, if (arr[j] > arr[j + 1]) compares the current element with its next neighbor. If the current element is larger (for ascending order), std::swap is used to exchange their positions.
5. Optimization Flag (swapped): A boolean variable swapped tracks if any swaps occurred during an entire pass of the inner loop. If a pass completes with swapped still being false, it means no elements were out of order, and thus the array is fully sorted. In this case, the outer loop breaks early, saving unnecessary comparisons.
6. Final Output: After the sorting process, the printArray function displays the now sorted arr.

Conclusion

Bubble Sort is a simple comparison-based sorting algorithm that, while not efficient for large datasets due to its O(n^2) time complexity, serves as an excellent foundational concept for understanding sorting. Its clear logic of repeatedly comparing and swapping adjacent elements makes it a great starting point for beginners in algorithm analysis.

Summary

• Purpose: Arranges elements of an array in a specified order (e.g., ascending).
• Mechanism: Iteratively compares adjacent elements and swaps them if they are in the wrong order.
• Efficiency: Has a time complexity of O(n^2) in the worst and average cases, making it less suitable for large datasets.
• Advantages: Simple to understand and implement, good for educational purposes or very small arrays.
• Optimization: Can be optimized by stopping early if no swaps occur in a pass, indicating the array is already sorted.