Bubble Sort in C++

Bubble Sort Algorithm in C++ (Complete Implementation).

BeginnerSorting & Searching ProgramsExample 1 of 13

bubble-sort.cpp

1#include <iostream>
2using namespace std;
3
4void bubbleSort(int arr[], int n) {
5    for (int i = 0; i < n - 1; i++) {
6        bool swapped = false;
7        for (int j = 0; j < n - i - 1; j++) {
8            if (arr[j] > arr[j + 1]) {
9                // Swap elements
10                swap(arr[j], arr[j + 1]);
11                swapped = true;
12            }
13        }
14        // If no swapping occurred, array is sorted
15        if (!swapped) break;
16    }
17}
18
19void printArray(int arr[], int n) {
20    for (int i = 0; i < n; i++) {
21        cout << arr[i] << " ";
22    }
23    cout << endl;
24}
25
26int main() {
27    int arr[] = {64, 34, 25, 12, 22, 11, 90};
28    int n = sizeof(arr) / sizeof(arr[0]);
29    
30    cout << "Original array: ";
31    printArray(arr, n);
32    
33    bubbleSort(arr, n);
34    
35    cout << "Sorted array: ";
36    printArray(arr, n);
37    
38    return 0;
39}

Output

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

What's going on

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.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

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

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

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

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

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

Optimization: Early Termination

bool swapped = false;

if (!swapped) break;

1// ... 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

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

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)

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

return 0;

This ends the program successfully.

Each pass parks the next-largest value at the end. The swapped flag skips extra passes on data that's already sorted. It's still O(n²) — fine for learning, not for a million items.

NextInsertion Sort