One pass of a bubble sort — Pseudocode Aptitude Question
One pass of a bubble sort: The array A is 0-indexed. What are the contents of A after the loop? Answer and worked solution on CodeKairo.
- Topic: Pseudocode
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 120 seconds
Question
The array A is 0-indexed. What are the contents of A after the loop?
Integer A[0..4], i, t
Set A = {5, 1, 4, 2, 8}
For i = 0 to 3
If A[i] > A[i + 1] Then
Set t = A[i]
Set A[i] = A[i + 1]
Set A[i + 1] = t
End If
End For
Print AOptions
- 1 2 4 5 8
- 1 4 2 5 8
- 1 4 5 2 8
- 5 1 4 2 8
Show the answer and the worked solution
Correct answer: B. 1 4 2 5 8
Worked solution
- i = 0: A[0] = 5 and A[1] = 1, so they are exchanged and the array becomes 1 5 4 2 8.
- i = 1: A[1] = 5 and A[2] = 4, so they are exchanged and the array becomes 1 4 5 2 8.
- i = 2: A[2] = 5 and A[3] = 2, so they are exchanged and the array becomes 1 4 2 5 8.
- i = 3: A[3] = 5 and A[4] = 8, and 5 > 8 is false, so nothing moves and the array printed is 1 4 2 5 8.
Answer: 1 4 2 5 8.
The idea
A single bubble pass carries the largest element to the end and leaves everything else only partly ordered. The fully sorted array 1 2 4 5 8 is the trap for anyone who assumes the whole sort has run.
Shortcut. Only 5 travels: it is larger than 1, 4 and 2, so it slides past each and stops before 8, and everything it passed shifts one place left, giving 1 4 2 5 8.
Common trap. "1 2 4 5 8" is the fully sorted array, chosen by assuming the whole sort has run when the code makes a single pass.