PPractick

The problem

You're explaining sorting to a class by lining students up by height. The simplest rule anyone can follow: walk down the line, and whenever two neighbours are in the wrong order, swap them. After one walk, the tallest student has "bubbled" to the end; repeat with the rest. That's bubble sort. It's slow in general, but with one small optimisation (stop as soon as a full pass makes no swaps) it detects an already sorted line in a single pass. It's also stable, which matters when sorting records by one field.

Example: [5, 1, 4, 2, 8] → [1, 2, 4, 5, 8].

Function signature

int bubbleSort(vector<int>& a);  // sorts in place; returns the number of passes made

Test cases

Input a	Output	Passes	Explanation
[5, 1, 4, 2, 8]	[1, 2, 4, 5, 8]	3	The third pass makes no swaps, so the loop stops early
[5, 2, 9, 1, 5, 6]	[1, 2, 5, 5, 6, 9]	4	Duplicates keep their relative order
[1, 2, 3]	[1, 2, 3]	1	Already sorted: one pass, no swaps, O(n)
[4, 3, 2, 1]	[1, 2, 3, 4]	3	Reverse order is the worst case
[42]	[42]	0	Nothing to compare
[]	[]	0

(Confirm: sort in place, non-decreasing; the early exit is expected; the code also cross-checks 1,000 random arrays against std::sort.)

How interviewers phrase it

• "Implement bubble sort. Can you optimise it for already sorted input?"
• Theory: "Is bubble sort stable? What's its best case?"
• "Why is bubble sort rarely used in practice?"

Clarifying questions to ask

1. Ascending order?
2. In place?
3. Should I include the early-exit optimisation?
4. Does stability matter?

Follow-ups to expect

1. "What does one pass guarantee?"
2. "What's the best case?"
3. "Worst case?"
4. "Is it stable?"
5. "Why is it slow in practice even among O(n²) sorts?"

Related questions

• Selection Sort Easy
• Insertion Sorting Easy
• Recursive Bubble Sort Easy
• Recursive Insertion Sort Easy
• Check if two strings are anagram of each other Easy
• Sort Characters by Frequency Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in