Bubble Sort

Easy10–15 min

Topics

SortingArray

Companies

AmazonAccenture

Given an array of integers, sort it in non-decreasing order using **Bubble Sort** — repeatedly sweep through the array, swapping adjacent elements that are out of order, until the whole array is sorted. Each full sweep pushes ("bubbles") the largest remaining value to its correct spot at the end, one position closer with every pass. It's one of the simplest sorting algorithms to reason about, and a natural first place to learn a key optimization idea: noticing when no work was done in a pass, and stopping early instead of grinding through passes that can't possibly change anything.

Test Case 1:

Input:arr = [7, 2, 9, 4, 2, 8]

Output:[2, 2, 4, 7, 8, 9]

Explanation:A typical unsorted array with a repeated value.

Test Case 2:

Input:arr = []

Output:[]

Explanation:An empty array is already sorted.

Test Case 3:

Input:arr = [5]

Output:[5]

Explanation:A single element is already sorted.

Constraints

◆0 ≤ arr.length ≤ 200
◆-1000 ≤ arr[i] ≤ 1000
◆Sort in non-decreasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Fixed Number of Passes

Good

Repeatedly sweep across the array, swapping any adjacent pair that's out of order — each full sweep "bubbles" the largest remaining value to its final position at the end. Doing this for n-1 sweeps guarantees the whole array is sorted. Correct, but it always runs every single sweep, even on a sweep where nothing needed swapping — there's no way to notice the array became sorted early and stop.

TimeO(n²)

SpaceO(1)

Java

Try it out

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

Optimal — Early Exit via Swapped Flag

Optimal

Same sweeping idea, but track whether a sweep actually swapped anything. If a whole sweep goes by with zero swaps, the array is already sorted — stop immediately instead of running the remaining sweeps for nothing. Worst case is still O(n²), but on data that's already sorted (or close to it) this finishes in a single O(n) pass.