Loading…

easyBasicsSometimes asked

Bubble Sort

Basics · 6 min

Given an integer array nums, sort it ascending using bubble sort (in place).

In plain English

Repeatedly swap adjacent out-of-order pairs; each pass 'bubbles' the largest remaining element to the end.

Examples

Example 1

Input: nums = [3, 1, 2]
Output: [1, 2, 3]
Note: Sorted.

Example 2

Input: nums = [1]
Output: [1]
Note: Already sorted.

Example 3

Input: nums = [2, 1]
Output: [1, 2]
Note: One swap.

Constraints

0 ≤ nums.length ≤ 10^3

Clarifying questions1First question: Must I implement it, or can I call a library sort?Explore questions

Q1.Must I implement it, or can I call a library sort?
I'll implement it since the algorithm is the point.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Nested loops: on each pass compare adjacent pairs and swap if out of order. An early-exit flag stops once a pass makes no swaps. O(n²) worst case.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know bubble sort's mechanics, the shrinking bound, and the early-exit optimisation.

Where candidates slip

No swap flag, or a non-shrinking inner bound.

How to stand out

Note it's stable and in place but O(n²); name a real-world sort for production.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Adjacent-swap passes

TimeO(n²)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each pass moves the largest unsorted element where?

2Hint 2Explore hint

Can you shrink the inner loop as elements settle?

3Hint 3Explore hint

Add a flag to stop early when a pass makes no swaps.

A · Core idea

Bubble sort makes repeated passes, swapping adjacent out-of-order pairs. Each pass 'bubbles' the largest remaining element to its final position at the end.

Why the inner bound shrinks (`n-1-i`). After pass i, the last i elements are already the i largest, sorted and settled — so the next pass needn't touch them. Shrinking the inner bound avoids redundant comparisons.

Why the early-exit flag matters. If a full pass makes zero swaps, the array is already sorted and you can stop — turning the best case (already-sorted input) into O(n). Without the flag it's always O(n²).

Stability and use. Bubble sort is stable (equal elements keep order) and in place (O(1) space), but its O(n²) average makes it a teaching algorithm, not a production one. Know it to discuss sorting fundamentals.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 1, 2]

pass1: 3,1

3>1 swap

State[1,3,2]

Final result[1, 2, 3]

C · Code with teaching comments

solution.javaJava

Adjacent-swap passes — optimal

2 teaching notes

1
public void bubbleSort(int[] nums) {
2
    for (int i = 0; i < nums.length - 1; i++) {
3
        boolean swapped = false;
4
        for (int j = 0; j < nums.length - 1 - i; j++) {
5
            if (nums[j] > nums[j + 1]) {
6
                int t = nums[j];
7
                nums[j] = nums[j + 1];
8
                nums[j + 1] = t;
9
                swapped = true;
10
            }
11
        }
12
        // No swaps means the array is sorted; stop early.
13
        if (!swapped) break;
14
    }
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — up to n passes of up to n comparisons → O(n²) worst/average; the swap flag makes a sorted input O(n).

E · Edge cases and pitfalls5nums = [1, 2, 3] — Already sorted → one pass, no swaps, O(n).Explore edge cases

Edge cases handled

nums = [1, 2, 3]Already sorted → one pass, no swaps, O(n).
nums = [1]Trivially sorted.
nums = [3, 2, 1]Worst case, full O(n²).

Pitfalls

Skipping the early-exit and always running O(n²).
Inner bound not shrinking (n-1-i), redoing settled elements.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void bubbleSort(int[] nums) { for (int i = 0; i < nums.length - 1; i++) { boolean swapped = false; for (int j = 0; j < nums.length - 1 - i; j++) { if (nums[j] > nums[j + 1]) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the early-exit and always running O(n²).
Inner bound not shrinking (n-1-i), redoing settled elements.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Adjacent-swap passes

Code pattern to memorize

for i: for j<n-1-i: if a[j]>a[j+1] swap; stop if no swaps

Rules to remember

1Swap out-of-order neighbours.
2Shrink inner bound by i.
3Early exit on a clean pass.

Use this pattern when

Teaching/illustrating adjacent-swap sorting

Choose another pattern when

Production sorting — use the library O(n log n)

Interview takeaway

Bubble sort: the largest bubbles to the end each pass.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Adjacent-swap passes. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

easyBasicsSometimes asked

Bubble Sort

Basics · 6 min

Given an integer array nums, sort it ascending using bubble sort (in place).

In plain English

Repeatedly swap adjacent out-of-order pairs; each pass 'bubbles' the largest remaining element to the end.

Examples

Example 1

Input: nums = [3, 1, 2]
Output: [1, 2, 3]
Note: Sorted.

Example 2

Input: nums = [1]
Output: [1]
Note: Already sorted.

Example 3

Input: nums = [2, 1]
Output: [1, 2]
Note: One swap.

Constraints

0 ≤ nums.length ≤ 10^3

Clarifying questions1First question: Must I implement it, or can I call a library sort?Explore questions

Q1.Must I implement it, or can I call a library sort?
I'll implement it since the algorithm is the point.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Nested loops: on each pass compare adjacent pairs and swap if out of order. An early-exit flag stops once a pass makes no swaps. O(n²) worst case.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know bubble sort's mechanics, the shrinking bound, and the early-exit optimisation.

Where candidates slip

No swap flag, or a non-shrinking inner bound.

How to stand out

Note it's stable and in place but O(n²); name a real-world sort for production.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Adjacent-swap passes

TimeO(n²)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Each pass moves the largest unsorted element where?

2Hint 2Explore hint

Can you shrink the inner loop as elements settle?

3Hint 3Explore hint

Add a flag to stop early when a pass makes no swaps.

A · Core idea

Bubble sort makes repeated passes, swapping adjacent out-of-order pairs. Each pass 'bubbles' the largest remaining element to its final position at the end.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 1, 2]

pass1: 3,1

3>1 swap

State[1,3,2]

Final result[1, 2, 3]

C · Code with teaching comments

solution.javaJava

Adjacent-swap passes — optimal

2 teaching notes

1
public void bubbleSort(int[] nums) {
2
    for (int i = 0; i < nums.length - 1; i++) {
3
        boolean swapped = false;
4
        for (int j = 0; j < nums.length - 1 - i; j++) {
5
            if (nums[j] > nums[j + 1]) {
6
                int t = nums[j];
7
                nums[j] = nums[j + 1];
8
                nums[j + 1] = t;
9
                swapped = true;
10
            }
11
        }
12
        // No swaps means the array is sorted; stop early.
13
        if (!swapped) break;
14
    }
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — up to n passes of up to n comparisons → O(n²) worst/average; the swap flag makes a sorted input O(n).

E · Edge cases and pitfalls5nums = [1, 2, 3] — Already sorted → one pass, no swaps, O(n).Explore edge cases

Edge cases handled

nums = [1, 2, 3]Already sorted → one pass, no swaps, O(n).
nums = [1]Trivially sorted.
nums = [3, 2, 1]Worst case, full O(n²).

Pitfalls

Skipping the early-exit and always running O(n²).
Inner bound not shrinking (n-1-i), redoing settled elements.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the early-exit and always running O(n²).
Inner bound not shrinking (n-1-i), redoing settled elements.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Adjacent-swap passes

Code pattern to memorize

for i: for j<n-1-i: if a[j]>a[j+1] swap; stop if no swaps

Rules to remember

1Swap out-of-order neighbours.
2Shrink inner bound by i.
3Early exit on a clean pass.

Use this pattern when

Teaching/illustrating adjacent-swap sorting

Choose another pattern when

Production sorting — use the library O(n log n)

Interview takeaway

Bubble sort: the largest bubbles to the end each pass.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Adjacent-swap passes. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern