Bubble Sort

Bubble Sort Algorithm in C++ (Complete Implementation)

BeginnerTopic: Sorting & Searching Programs
Back

C++ Bubble Sort Program

This program helps you to learn the fundamental structure and syntax of C++ programming.

Try This Code
#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

Understanding Bubble Sort

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

This header provides:

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

---

#include <iostream>

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;

if (!swapped) break;

// ... inner loop ...

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.

Let us now understand every line and the components of the above program.

Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.

Practical Learning Notes for Bubble Sort

This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.

A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.

For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.

Next
Insertion Sort
Next
Insertion Sort

Table of Contents