Bubble Sort in C, C++, and Java: Code and Complexity

Bubble sort compares adjacent elements and swaps them if they are out of order, repeating across the array until no swaps are needed.

The algorithm’s appeal in placement interviews is not speed. It’s transparency. Every comparison and every swap is visible in the trace, which makes it the easiest sorting algorithm to demonstrate step by step on a whiteboard. Interviewers at TCS, Infosys, Cognizant, and Wipro include it in technical rounds to check whether candidates can state complexity without prompting and know when not to use it.

What Bubble Sort Does

The core operation: scan the array from index 0 to n-2, comparing arr[j] with arr[j+1]. If arr[j] is greater, swap the two elements. Repeat this scan n-1 times. After each complete scan, the largest unsorted element has moved to its correct position at the right end of the remaining unsorted segment.

Three properties worth stating before writing the code:

• In-place: no auxiliary array is needed; swaps happen within the original array.
• Stable: equal elements are never exchanged (the condition is strictly arr[j] > arr[j+1]), so their relative order is preserved.
• Adaptive: with the early-exit flag covered in a later section, the algorithm exits as soon as no swap occurs in a full pass.

The pseudocode makes the two nested loops explicit:

for i = 0 to n-2:
    for j = 0 to n-i-2:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])

The outer loop runs n-1 times. The inner loop’s upper bound shrinks by one each iteration because the last i positions are already in their final order.

Step-by-Step Trace

Start with [5, 3, 8, 4, 2] (n = 5, so 4 passes are needed).

Pass 1

• 5 vs 3: 5 is greater, swap → [3, 5, 8, 4, 2]
• 5 vs 8: 5 is not greater, no swap → [3, 5, 8, 4, 2]
• 8 vs 4: 8 is greater, swap → [3, 5, 4, 8, 2]
• 8 vs 2: 8 is greater, swap → [3, 5, 4, 2, 8]

Result after pass 1: 8 is at index 4, its correct final position.

Pass 2

• 3 vs 5: no swap → [3, 5, 4, 2, 8]
• 5 vs 4: swap → [3, 4, 5, 2, 8]
• 5 vs 2: swap → [3, 4, 2, 5, 8]

Result after pass 2: 8 and 5 are both settled at the right end.

Pass 3

• 3 vs 4: no swap → [3, 4, 2, 5, 8]
• 4 vs 2: swap → [3, 2, 4, 5, 8]

Result after pass 3: 8, 5, and 4 are in their correct positions.

Pass 4

• 3 vs 2: swap → [2, 3, 4, 5, 8]

Final sorted array: [2, 3, 4, 5, 8].

Code in C, C++, and Java

Bubble Sort in C

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp   = arr[j];
                arr[j]     = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

C has no built-in swap function, so the exchange uses a temporary variable. The inner loop bound n - i - 1 avoids re-comparing the already-sorted tail elements on every pass.

Bubble Sort in C++

#include <iostream>
#include <algorithm>   // std::swap
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

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

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: ";
    printArray(arr, n);
    return 0;
}

The C++ version calls std::swap from <algorithm>. Using std::swap rather than a manual temp variable communicates intent more directly, and the compiler generates the same machine instructions either way.

Bubble Sort in Java

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp   = arr[j];
                    arr[j]     = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        System.out.println("Sorted: " + Arrays.toString(arr));
    }
}

Java has no standalone swap function for primitives, so the temp-variable pattern from C reappears here. Arrays.toString formats the output without a manual loop.

Optimised Bubble Sort

The basic implementation runs n-1 passes regardless of the input state. If the array happens to be fully sorted after pass 2, passes 3 through n-1 still execute, each doing zero useful work.

The fix is a boolean flag. Set it to false before each pass. If any swap occurs, set it to true. After the inner loop finishes, check the flag: if it is still false, no swap occurred, the array is sorted, and the outer loop can break early.

void optimisedBubbleSort(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;
    }
}

Apply the same flag in C (use int swapped = 0) or Java (use boolean swapped = false). The change is four lines and drops the best-case from O(n²) to O(n) for an already-sorted or nearly-sorted input.

Time and Space Complexity

Case	Time	Notes
Worst case	O(n²)	Reverse-sorted input; every comparison triggers a swap
Average case	O(n²)	Random input; most comparisons trigger swaps
Best case	O(n)	Already-sorted input with the early-exit flag active

Space complexity is O(1). Bubble sort is in-place. The only extra storage is the temp variable and, in the optimised version, the swapped flag; both are constant regardless of input size.

The O(n²) cost matters in placement interviews because the follow-up question is almost always “when would you not use this?” The expected answer: bubble sort is appropriate for small or nearly-sorted arrays. For general-purpose sorting, NPTEL’s IIT Madras algorithms course covers merge sort and quicksort, which replace bubble sort for any input beyond a few dozen elements.

When to Use and When to Replace Bubble Sort

Use bubble sort when:

• The array has under 20 elements and runtime is not a constraint.
• The input is nearly sorted and the early-exit flag is active.
• You are writing a teaching example or tracing the sort on paper for an interview question.

Replace bubble sort when:

• The array is large: O(n²) comparisons grow steeply as element count increases.
• Write operations are expensive (such as on flash storage): selection sort makes at most one write per pass, versus bubble sort’s many intermediate swaps.
• You need production-grade speed: std::sort in C++ and Arrays.sort in Java both run in O(n log n) time using hybrid algorithms.

The step-by-step tracing instinct that bubble sort builds is the same instinct interviewers test in data structures interview questions, where candidates are expected to walk through array operations index by index. The same analytical approach applies to FACE Prep’s guide on finding the smallest and largest element in an array, which uses an analogous single-pass scan with two running candidates.

Bubble sort makes trade-offs explicit: every comparison is visible, every swap is intentional, and the O(n²) cost is the price of simplicity. That build-and-trace instinct carries into AI work. If you want to apply it to LLM projects without committing to a longer programme, TinkerLLM starts at ₹299 for the first month.