Selection sort

Selection sort is the most intuitive algorithm: at each step, you look for the smallest element still left to sort, then you swap it with the first unsorted element. This is exactly what you would do when sorting cards by hand: you spot the smallest card in the remaining pile, take it out, and put it in its place.

The principle in detail: for each position i (from 0 to n-2), you scan the rest of the array (from i to n-1) to find the index of the minimum, then you swap (exchange) that element with the one at position i. After pass number i, the first i+1 elements are definitively in their final place.

Watch the array transform step by step on the example [5, 2, 4, 1, 3]:

start   : [5, 2, 4, 1, 3]
step 0  : [1, 2, 4, 5, 3]   (minimum found at index 3, swapped with index 0)
step 1  : [1, 2, 4, 5, 3]   (minimum of the rest already at position 1, no useful swap)
step 2  : [1, 2, 3, 5, 4]   (minimum found at index 4, swapped with index 2)
step 3  : [1, 2, 3, 4, 5]   (minimum found at index 4, swapped with index 3)

sorted part (on the left) | part to sort (on the right)

The cost: for each position i, you scan about n-i elements to find the minimum. In total, that makes n + (n-1) + ... + 1, i.e. about n²/2 comparisons. Selection sort is therefore O(n²), whatever the initial state of the array (even already sorted, it redoes all the comparisons). Its advantage: very few swaps (at most n-1), which is useful when swapping is expensive.

def tri_selection(a):
    a = a[:]
    n = len(a)
    for i in range(n - 1):
        indice_min = i
        for j in range(i + 1, n):
            if a[j] < a[indice_min]:
                indice_min = j
        a[i], a[indice_min] = a[indice_min], a[i]
    return a

Classic pitfall: forgetting to update indice_min (comparing with a[i] instead of a[indice_min]), which breaks the search for the minimum.