How many swaps does it perform — Aptitude Question
How many swaps does it perform: The array A is 0-indexed. What is printed? Answer and worked solution on CodeKairo.
- Topic: Pseudocode
- Section: Programming MCQs
- Difficulty: Hard
- Time target: 150 seconds
Question
The array A is 0-indexed. What is printed?
Integer A[0..3], i, j, m, t, swaps
Set A = {4, 3, 2, 1}
Set swaps = 0
For i = 0 to 2
Set m = i
For j = i + 1 to 3
If A[j] < A[m] Then
Set m = j
End If
End For
If m != i Then
Set t = A[i]
Set A[i] = A[m]
Set A[m] = t
Set swaps = swaps + 1
End If
End For
Print swapsOptions
- 2
- 3
- 4
- 6
Show the answer and the worked solution
Correct answer: A. 2
Worked solution
- i = 0: the minimum of 4, 3, 2, 1 is 1 at index 3, so the swap happens and A becomes 1 3 2 4. swaps = 1.
- i = 1: the minimum of 3, 2, 4 is 2 at index 2, so the swap happens and A becomes 1 2 3 4. swaps = 2.
- i = 2: the minimum of 3, 4 is 3, already at index 2, so m equals i and the guarded swap is skipped.
- The loop ends with swaps = 2.
Answer: 2.
The idea
Selection sort does at most n − 1 swaps regardless of how scrambled the input is, and the guard m != i removes even those that would move an element onto itself. Counting comparisons instead of swaps gives 6, the distractor.
Shortcut. Reversing 4 3 2 1 needs just two exchanges, 4↔1 and 3↔2; each selection pass makes one of them, and the guard skips the last pass.
Common trap. 3 assumes selection sort always makes n − 1 = 3 swaps and misses the m != i guard, which skips the third pass because 3 is already in place.