Selection Sort
Pick the smallest each time.
Selection sort is how many people sort playing cards. Find the smallest card, and put it first. Then find the smallest of the rest, and put it second. Keep going until you run out of cards.

- Find the smallest
- Put it first
- Repeat with the rest
Choosing the smallest
For each position, we search the rest of the list for the smallest item. Then we swap it into place. The part on the left grows, and it's always sorted. Run it. After each pass, one more item is in its final place, from left to right.
def selection_sort(nums):
n = len(nums)
for i in range(n - 1):
smallest = i
for j in range(i + 1, n):
if nums[j] < nums[smallest]:
smallest = j
nums[i], nums[smallest] = nums[smallest], nums[i]
print(f"pass {i + 1}: {nums}")
selection_sort([5, 2, 9, 1, 7])pass 1: [1, 2, 9, 5, 7] pass 2: [1, 2, 9, 5, 7] pass 3: [1, 2, 5, 9, 7] pass 4: [1, 2, 5, 7, 9]
Selection sort cost
Selection sort is also O of N squared, because finding the smallest is a loop, inside a loop over every position. But it makes very few swaps, at most N, which can matter when moving items is expensive. Like bubble sort, it's mostly for learning.
| key | value |
|---|---|
| Time | O(n²) |
| Swaps | at most n |
| Space | O(1) |
| Use | learning, few swaps |
Summary
Selection sort picks the smallest remaining item, and swaps it into place. It's O of N squared, with few swaps. Next, insertion sort, which is surprisingly useful.
Key takeaways- Find the smallest
- Swap it into place
- O(n²)