Past exam question: 2074 Bhadra (Regular), Q8
Open in the Padhaiko appQuestion
Explain selection sort. Sort data sequence 40 90 20 -10 30 5 60 100 80 using selection sort method.
Solution
Selection Sort Algorithm: Selection sort repeatedly selects the smallest element from the unsorted subarray A[i..n-1] and swaps it into position A[i] for . It performs comparisons in all cases ( time, space).
Pass-by-Pass Trace on [40, 90, 20, -10, 30, 5, 60, 100, 80]:
- Pass 1 (): min
-10(idx 3)40:[-10 | 90, 20, 40, 30, 5, 60, 100, 80] - Pass 2 (): min
5(idx 5)90:[-10, 5 | 20, 40, 30, 90, 60, 100, 80] - Pass 3 (): min
20(idx 2, in place):[-10, 5, 20 | 40, 30, 90, 60, 100, 80] - Pass 4 (): min
30(idx 4)40:[-10, 5, 20, 30 | 40, 90, 60, 100, 80] - Pass 5 (): min
40(idx 4, in place):[-10, 5, 20, 30, 40 | 90, 60, 100, 80] - Pass 6 (): min
60(idx 6)90:[-10, 5, 20, 30, 40, 60 | 90, 100, 80] - Pass 7 (): min
80(idx 8)90:[-10, 5, 20, 30, 40, 60, 80 | 100, 90] - Pass 8 (): min
90(idx 8)100:[-10, 5, 20, 30, 40, 60, 80, 90, 100]
Answer:
Sorted sequence: -10, 5, 20, 30, 40, 60, 80, 90, 100.