Selection Sort and Insertion Sort

Selection sort: pick the smallest

Find the smallest item and put it first. Then find the smallest of the rest and put it second. And so on.

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]
    return nums

print(selection_sort([64, 25, 12, 22, 11]))

Output

[11, 12, 22, 25, 64]

Insertion sort: like sorting cards in your hand

Think of it like this: When you pick up playing cards one at a time, you slide each new card left past the bigger cards until it sits in the right place. Your hand is always sorted.

def insertion_sort(nums):
    for i in range(1, len(nums)):
        card = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > card:    # shift bigger cards right
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = card                  # drop the card in the gap
        print(nums)
    return nums

insertion_sort([7, 3, 5, 1])

Output

[3, 7, 5, 1]
[3, 5, 7, 1]
[1, 3, 5, 7]

Comparing the simple sorts

Remember: Insertion sort is genuinely useful: for small or almost-sorted lists it beats fancier sorts. Python's own sort uses it on small pieces.