Bubble Sort looks easy, which is why it catches students who memorise only O(n^2). DSSSB, RSSB, ISRO, and GATE questions also test best-case assumptions, the array state after a named pass, and exact swap counts. For any trace, compare adjacent elements from left to right and remember that each completed pass fixes the largest remaining value at the right edge. For swap questions, count inversions instead of drawing every pass; for best-case questions, first check whether the implementation has a swapped flag.
Complexity questions every exam asks first
Worst case and best case form one contrast. DSSSB asked this pattern in 2018 and again in 2021, so learn the rule precisely.
Q1. Worst-case time complexity
DSSSB 2018: see the solved page
"What is the worst-case time complexity of Bubble Sort?"
(a) O(n)
(b) O(n^2)
(c) O(n log n)
(d) O(n^3)
Answer: (b) O(n^2). A reverse-sorted input forces every adjacent out-of-order pair to move. The passes make (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 comparisons, so the growth rate is O(n^2).
Q2. Best-case time complexity
TPSC 2025: see the solved page
"What is the best-case time complexity for the Bubble Sort algorithm ?"
(a) O(n)
(b) O(n log n)
(c) O(n^2)
(d) O(log n)
Answer: (a) O(n). This best case requires the optimised version with a swapped flag. One pass over an already sorted array makes no swaps, so the flag stops the algorithm; plain Bubble Sort without that check still takes O(n^2) time.
Pass-tracing questions: what the array looks like mid-sort
After pass k, the k largest elements are fixed at the end in sorted order. During the pass, the largest remaining value moves right past smaller neighbours.
Q3. Trace the first pass
RSSB 2022: see the solved page
"What will be the output list after completing first pass of bubble sort on input array 32, 51, 27, 85, 66, 23, 13, 57 ?"
(a) 32, 27, 51, 66, 23, 13, 57, 85
(b) 32, 51, 27, 66, 23, 13, 57, 8
(c) 27, 33, 51, 23, 13, 57, 66, 85
(d) 23, 13, 27, 33, 51, 57, 66, 85
Answer: (a). Compare 32 and 51, no swap. Swap 51 with 27 to get 32, 27, 51, 85, 66, 23, 13, 57; compare 51 and 85, no swap; then swap 85 successively with 66, 23, 13, and 57. Pass 1 ends as 32, 27, 51, 66, 23, 13, 57, 85, with 85 locked in the last slot.
Q4. Trace the second pass
DSSSB 2021: see the solved page
"Sort the following elements using Bubble sort in ascending order. What is the intermediate sequence of 37, 54, 21, 85, 68, 12, 9, 57 after second pass?"
(a) 21, 37, 12, 9, 54, 57, 68, 85
(b) 37, 21, 54, 68, 12, 9, 57, 85
(c) 21, 37, 54, 12, 9, 57, 68, 85
(d) 21, 12, 9, 37, 54, 57, 68, 85
Answer: (c). Pass 1 produces 37, 21, 54, 68, 12, 9, 57, 85. In pass 2, 37 swaps with 21, then 68 moves past 12, 9, and 57, giving 21, 37, 54, 12, 9, 57, 68, 85. The locked-tail rule immediately rules out (b), but tracing is needed to distinguish the other choices.
Swap-counting questions: use the inversion shortcut
Bubble Sort swaps equal the number of inversions, or pairs in the wrong order. Each adjacent swap fixes one inversion, so count smaller values to the right instead of simulating every pass.
Q5. Swaps needed to sort SORTED
DSSSB 2021: see the solved page
"How many interchanges will happen when the sequence of letters of "SORTED" is sorted using bubble sort?"
(a) 36
(b) 11
(c) 18
(d) 6
Answer: (b) 11. The alphabetical target is D, E, O, R, S, T. S contributes 4 inversions with O, R, E, D; O contributes 2 with E, D; R contributes 2 with E, D; T contributes 2 with E, D; and E contributes 1 with D. Total: 4 + 2 + 2 + 2 + 1 = 11.
Q6. Swaps for seven numbers
ISRO 2017: see the solved page
"The number of swappings needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order, using bubble sort is"
(a) 11
(b) 12
(c) 13
(d) 10
Answer: (d) 10. The contributions are: 8 > 7, 5, so 2; 22 > 7, 9, 5, 13, so 4; 7 > 5, so 1; 9 > 5, so 1; and 31 > 5, 13, so 2. Thus 2 + 4 + 1 + 1 + 2 = 10.
Q7. Another inversion count
BEL 2023: see the solved page
"What is the total number of swaps performed to sort the following list of elements 18, 32, 17, 19, 41, 15, 23 in an ascending order, using bubble sort?"
(a) 12
(b) 13
(c) 10
(d) 11
Answer: (c) 10. Count 2 from 18, which exceeds 17 and 15; 4 from 32, which exceeds 17, 19, 15, and 23; 1 each from 17 and 19, both exceeding 15; and 2 from 41, which exceeds 15 and 23. The sum is 2 + 4 + 1 + 1 + 2 = 10.
Q8. A five-element array
CoCubes 2023: see the solved page
"How many swaps are required to sort the given array using bubble sort - { 2, 5, 1, 3, 4}"
(a) 4
(b) 5
(c) 6
(d) 7
Answer: (a) 4. The value 2 forms one inversion with 1. The value 5 forms three with 1, 3, and 4, giving 1 + 3 = 4; inversion counting avoids a full pass-by-pass simulation.
Optimised Bubble Sort and the flag variable
The swapped flag stops Bubble Sort after the first clean pass. Selection Sort still performs exactly n - 1 outer iterations, regardless of input order.
Q9. Sorted input with a flag
Placement practice question: see the solved page
"The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The number of iterations in selection sort and bubble sort respectively are __________"
(a) 5 and 4
(b) 1 and 4
(c) 0 and 4
(d) 4 and 1
Answer: (d) 4 and 1. Selection Sort performs n - 1 = 4 iterations. Flagged Bubble Sort makes one pass, records zero swaps, and stops.
Q10. Iterations on unsorted input
Placement practice question: see the solved page
"The given array is arr = {3, 4, 5, 2, 1}. The number of iterations in bubble sort and selection sort respectively are __________"
(a) 5 and 4
(b) 4 and 5
(c) 2 and 4
(d) 2 and 5
Answer: (a) 5 and 4. The Bubble Sort passes produce 3, 4, 2, 1, 5, then 3, 2, 1, 4, 5, then 2, 1, 3, 4, 5, and finally 1, 2, 3, 4, 5. Under the question's flag-based iteration convention, a fifth clean check confirms that no swaps remain; Selection Sort performs n - 1 = 4 iterations.
Q11. What the flag does not improve
Placement practice question: see the solved page
"Which of the following is not an advantage of optimised bubble sort over other sorting techniques in case of sorted elements?"
(a) It is faster
(b) Consumes less memory
(c) Detects whether the input is already sorted
(d) Consumes less time
Answer: (b) Consumes less memory. The flag adds early termination, which improves time and detects sorted input. It does not reduce the algorithm's O(1) extra-space requirement, so lower memory use is not an advantage created by the optimisation.
The GATE 2025 numerical answer question
A NAT, or numerical answer type, requires a numerical answer rather than an option choice. Review GATE question types: MCQ, MSQ and NAT if the format is unfamiliar.
Q12. Maximum swaps on 30 elements
GATE 2025 NAT: see the solved page
"The pseudocode of a function fun() is given below:
fun(int A[0, ... , n-1])
{
for i = 0 to n-2
for j = 0 to n-i-2
if (A[j] > A[j+1])
then swap A[j] and A[j+1]
}Let A[0, ... , 29] be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with A[0, ... , 29] as argument, is __________. (Answer in integer)"
Answer: 435. Descending order makes every pair an inversion. Therefore swaps equal C(30, 2) = 30 x 29 / 2 = 435, which is the maximum-swap formula n(n - 1)/2 applied to 30 elements.
How exams test Bubble Sort
Question pattern | Rule to apply |
|---|---|
Complexity case |
|
Array after pass | The |
Number of swaps | Count inversions in the input |
Maximum swaps | Use |
Revise the wider theory with Sorting algorithms: comparison and complexity. Its comparison table places Bubble Sort beside Selection, Insertion, Merge, Heap, and Quick Sort on time, space, and stability.
The short version and your next step
Remember three things: identify whether the question means plain or flagged Bubble Sort, lock one more maximum at the end after each pass, and replace swap simulation with inversion counting. For GATE preparation, GATE Guidance by Sanchit Sir includes the Algorithms module and solved PYQ pages. Placement aspirants can study sorting with the rest of DSA in Coding for Placements: C, C++, Java, Python, while the Coding & DSA Courses for Placements page collects the wider course path.
