Selection Sort

The Idea

Scan the unsorted part for its smallest value and swap it into the next position. Each round locks one element into its final home. Comparisons are always O(n²), but there are at most n swaps.

Real-World Example

A sports draft works this way. Every round each team looks over the remaining players, takes the best one still available, and the pool shrinks by one. The picking order ends up ranked by quality.

The Code

def selection_sort(nums):
    n = len(nums)
    for i in range(n):
        smallest = i
        for j in range(i + 1, n):       # scan the unsorted tail
            if nums[j] < nums[smallest]:
                smallest = j
        # one swap per round, at most n swaps in total
        nums[i], nums[smallest] = nums[smallest], nums[i]
    return nums
# selection_sort([64, 25, 12, 22]) -> [12, 22, 25, 64]

nums = [3, 1, 2]
smallest = 0
for j in range(1, 3):
  # track the index of the minimum
  if nums[j] ___ nums[smallest]:
      smallest = j