Past exam question: 2076 Baisakh (Back), Q9
Open in the Padhaiko appQuestion
Explain selection sort. Sort the numbers 92, 73, 22, 49, 46, 98, 21, 9, 70 and 63 using selection sort.
Solution
Working Principle of Selection Sort: Selection sort partitions the array into a sorted prefix A[0..i-1] and an unsorted suffix A[i..n-1]. In each pass , it scans the unsorted suffix to find the index minIdx of the smallest element and swaps A[i] with A[minIdx].
- Time Complexity: in best, average, and worst cases ( comparisons).
- Space Complexity: in-place; at most swaps.
Pass-by-Pass Trace on [92, 73, 22, 49, 46, 98, 21, 9, 70, 63]:
- Pass 1 (): min in
0..9is9(idx 7)92:[9 | 73, 22, 49, 46, 98, 21, 92, 70, 63] - Pass 2 (): min in
1..9is21(idx 6)73:[9, 21 | 22, 49, 46, 98, 73, 92, 70, 63] - Pass 3 (): min in
2..9is22(idx 2, already in place):[9, 21, 22 | 49, 46, 98, 73, 92, 70, 63] - Pass 4 (): min in
3..9is46(idx 4)49:[9, 21, 22, 46 | 49, 98, 73, 92, 70, 63] - Pass 5 (): min in
4..9is49(idx 4, already in place):[9, 21, 22, 46, 49 | 98, 73, 92, 70, 63] - Pass 6 (): min in
5..9is63(idx 9)98:[9, 21, 22, 46, 49, 63 | 73, 92, 70, 98] - Pass 7 (): min in
6..9is70(idx 8)73:[9, 21, 22, 46, 49, 63, 70 | 92, 73, 98] - Pass 8 (): min in
7..9is73(idx 8)92:[9, 21, 22, 46, 49, 63, 70, 73 | 92, 98] - Pass 9 (): min in
8..9is92(idx 8, already in place):[9, 21, 22, 46, 49, 63, 70, 73, 92, 98]
Answer:
Sorted sequence using selection sort: 9, 21, 22, 46, 49, 63, 70, 73, 92, 98.