Sort the following list using the selection sort algorithm. H, V, A, T, L, N,…
2021
Sort the following list using the selection sort algorithm. H, V, A, T, L, N, K What is the output of the algorithm after the 3rd pass?
- A.
A, V, H, T, L, N, K
- B.
A, H, K, T, L, N, V
- C.
A, V, T, H, L, N, K
- D.
A, T, H, K, L, N, V
Attempted by 636 students.
Show answer & explanation
Correct answer: B
Concept
Selection sort builds the sorted part one position at a time. On each pass it scans the entire unsorted region, finds the single minimum element there, and swaps that minimum into the first unsorted slot. After k passes, the k smallest elements of the whole list occupy the first k positions in order, and the rest of the list is whatever the swaps left behind.
Applying it to H, V, A, T, L, N, K
Scan all of H, V, A, T, L, N, K; the minimum is A. Swap A with the first element H, giving A, V, H, T, L, N, K.
Scan the unsorted part V, H, T, L, N, K; the minimum is H. Swap H with the first unsorted element V, giving A, H, V, T, L, N, K.
Scan the unsorted part V, T, L, N, K; the minimum is K. Swap K with the first unsorted element V, giving A, H, K, T, L, N, V.
After the 3rd pass the list is A, H, K, T, L, N, V.
Cross-check
Each pass advances the boundary of the sorted region by one and places the smallest remaining letter there, so after three passes exactly three letters are finalised at the front and the tail is still the unsorted remainder. Re-running a single pass on the result above would only touch that tail, confirming the front three are already settled.