Topic: Algorithms
Which of the following sorting technique was applied for an input array {10, 5, 16, 2, 8, 9} which gives array {2, 5, 10, 16, 8, 9} after three iterations?
- A. Bubble sort
- B. Selection sort
- C. Insertion sort
- D. All of the above
Answer: C. Insertion sort
Explanation: Let's trace Insertion Sort for the array {10, 5, 16, 2, 8, 9}:
- Initial: {10, 5, 16, 2, 8, 9}
- Iteration 1 (insert 5): 5 is compared with 10 and swapped. Array becomes {5, 10, 16, 2, 8, 9}.
- Iteration 2 (insert 16): 16 is compared with 10. No swap needed. Array remains {5, 10, 16, 2, 8, 9}.
- Iteration 3 (insert 2): 2 is smaller than 16, 10, and 5. It is inserted at the beginning. Array becomes {2, 5, 10, 16, 8, 9}.
This matches the given result exactly.