C++/Sorting & Searching Programs/Program

Bubble Sort

Bubble Sort Algorithm in C++ (Complete Implementation)

C++Beginner
C++
Try
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // If no swapping occurred, array is sorted
        if (!swapped) break;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array: ";
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    cout << "Sorted array: ";
    printArray(arr, n);
    
    return 0;
}

Output

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

This program teaches you how to implement the Bubble Sort algorithm in C++. Bubble Sort is one of the simplest sorting algorithms, making it excellent for learning sorting concepts. Although not efficient for large datasets, it's easy to understand and implement, making it a fundamental algorithm for beginners.

1. What This Program Does

The program sorts an array of integers using the Bubble Sort algorithm. For example:

  • Input array: [64, 34, 25, 12, 22, 11, 90]
  • Output array: [11, 12, 22, 25, 34, 64, 90]

Bubble Sort works by repeatedly comparing adjacent elements and swapping them if they're in the wrong order, "bubbling" the largest elements to the end in each pass.

2. Header File Used

#include <iostream>

This header provides:

  • cout for displaying output
  • cin for taking input from the user

3. Understanding Bubble Sort

Algorithm Concept:

  • Compare adjacent elements
  • Swap if they're in wrong order
  • Largest element "bubbles" to the end
  • Repeat for remaining elements

Visual Example:

Initial: [64, 34, 25, 12, 22, 11, 90]

Pass 1: Compare and swap adjacent pairs

  • 64 > 34 → swap: [34, 64, 25, 12, 22, 11, 90]
  • 64 > 25 → swap: [34, 25, 64, 12, 22, 11, 90]
  • 64 > 12 → swap: [34, 25, 12, 64, 22, 11, 90]
  • 64 > 22 → swap: [34, 25, 12, 22, 64, 11, 90]
  • 64 > 11 → swap: [34, 25, 12, 22, 11, 64, 90]
  • 64 < 90 → no swap
  • After Pass 1: largest (90) is at end

Pass 2: Repeat for remaining elements

  • Continue until array is sorted

4. Function: bubbleSort()

void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { bool 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; } }

How it works:

  • Outer loop (i): controls number of passes (n - 1 passes needed)
  • Inner loop (j): compares adjacent elements (0 to n - i - 1)
  • swapped flag: tracks if any swap occurred
  • Early termination: if no swaps, array is sorted

5. Step-by-Step Algorithm

Pass 1 (i = 0):

  • Compare arr[0] with arr[1], swap if needed
  • Compare arr[1] with arr[2], swap if needed
  • Continue to arr[n-2] with arr[n-1]
  • Largest element moves to position n-1

Pass 2 (i = 1):

  • Compare elements from 0 to n-2
  • Second largest moves to position n-2
  • Continue until array is sorted

Optimization:

  • swapped flag detects if array is already sorted
  • If no swaps in a pass, array is sorted
  • Early termination improves best-case performance

6. Understanding the Loops

Outer Loop: for (int i = 0; i < n - 1; i++)

  • Runs n - 1 times (maximum passes needed)
  • Each pass places one element in correct position
  • After n - 1 passes, all elements are sorted

Inner Loop: for (int j = 0; j < n - i - 1; j++)

  • Compares adjacent pairs: arr[j] and arr[j + 1]
  • Range decreases each pass: n - i - 1
  • After pass i, last i elements are already sorted

Why n - i - 1?:

  • After pass 1, last 1 element is sorted (don't compare)
  • After pass 2, last 2 elements are sorted (don't compare)
  • Reduces unnecessary comparisons

7. Swap Operation

if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swapped = true; }

How it works:

  • Compares adjacent elements
  • If left > right, they're in wrong order
  • swap() exchanges their positions
  • Sets swapped flag to true

Example:

  • Before: arr[j] = 64, arr[j+1] = 34
  • Condition: 64 > 34 → true
  • After swap: arr[j] = 34, arr[j+1] = 64

8. Optimization: Early Termination

bool swapped = false; // ... inner loop ... if (!swapped) break;

How it works:

  • swapped flag tracks if any swap occurred
  • If no swaps in a pass, array is already sorted
  • break exits outer loop early
  • Improves best-case time complexity to O(n)

Example:

  • Array: [1, 2, 3, 4, 5] (already sorted)
  • Pass 1: no swaps → break immediately
  • Only one pass needed instead of n - 1

9. Time and Space Complexity

Time Complexity:

  • Worst case: O(n²) - array in reverse order
  • Best case: O(n) - array already sorted (with optimization)
  • Average case: O(n²)

Space Complexity: O(1)

  • Only uses constant extra space
  • Sorts in-place (modifies original array)

Stability: Stable

  • Equal elements maintain their relative order
  • Important for sorting objects with multiple fields

10. When to Use Bubble Sort

Educational Purposes:

  • Learning sorting algorithms
  • Understanding basic sorting concepts
  • Teaching algorithm visualization

Small Datasets:

  • Efficient enough for small arrays (< 100 elements)
  • Simple implementation
  • Low overhead

Nearly Sorted Data:

  • With optimization, very fast for nearly sorted arrays
  • O(n) best case performance

Not Recommended For:

  • Large datasets (use Quick Sort, Merge Sort)
  • Performance-critical applications
  • Real-world production code (usually)

11. Important Considerations

Array Bounds:

  • Inner loop: j < n - i - 1 (prevents out-of-bounds)
  • arr[j + 1] must be valid index
  • Careful with loop boundaries

Optimization:

  • Always use swapped flag for early termination
  • Significantly improves best-case performance
  • No additional space cost

In-Place Sorting:

  • Modifies original array
  • If you need original, make a copy first
  • Space-efficient approach

12. return 0;

This ends the program successfully.

Summary

  • Bubble Sort repeatedly compares and swaps adjacent elements.
  • Time complexity: O(n²) worst/average, O(n) best (optimized).
  • Space complexity: O(1) - sorts in-place.
  • Optimization with swapped flag enables early termination.
  • Simple to understand but inefficient for large datasets.
  • Stable algorithm - maintains relative order of equal elements.
  • Best for learning, small datasets, or nearly sorted data.
  • Understanding Bubble Sort is foundation for learning other sorting algorithms.

This program is fundamental for beginners learning sorting algorithms, understanding time complexity, and preparing for more efficient sorting algorithms like Quick Sort and Merge Sort in C++ programs.

Next
Insertion Sort