Pick the smallest, then move on
Each pass finds the smallest value left and swaps it to the front. About 8 minutes.
Find the smallest of what's left
Think of picking a team: each round you scan everyone still waiting and pick the best one. Pass number i looks only at positions i and after, because everything before is already settled from earlier passes.
Scan that stretch and remember the position of the smallest value you have seen so far, in a variable often called best.
Pass 1: the smallest value anywhere is 1, at index 3. Swap it to index 0.
Swap it to the front, then move on
Once the scan ends, swap the smallest value into the first position of the stretch. That value is now settled for good, and the next pass never touches that position again. Then the start of the stretch moves forward by one.
Each pass does at most one swap, which is why this sort is gentle on writes.
n = len(nums)
for i in range(k):
best = i
for j in range(i + 1, n):
if nums[j] < nums[best]:
best = j
tmp = nums[i]
nums[i] = nums[best]
nums[best] = tmp
return numsnums = [6, 2, 7, 1, 9]. What does nums look like after one pass of selection sort?
- A[1, 2, 7, 6, 9]
- B[1, 2, 6, 7, 9]
- C[6, 2, 7, 1, 9]
Show the answer
[1, 2, 7, 6, 9]. The smallest value anywhere is 1, at index 3. Swapping it with index 0 gives [1, 2, 7, 6, 9].
After k passes
Selection sort works in passes. Pass i (starting at i = 0) scans nums from index i to the end, finds the smallest value in that stretch, and swaps it into index i. Return nums after exactly k passes (k = 0 means no passes at all).
nums = [5, 3, 8, 1, 9, 2], k = 2 → [1, 2, 8, 5, 9, 3]
0 ≤ k ≤ n ≤ 100,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000