Trier une liste

L = [5, 2, 9, 1]
print(sorted(L))   # [1, 2, 5, 9] — une NOUVELLE liste
print(L)           # [5, 2, 9, 1] — inchangée

print(L.sort())    # None !
print(L)           # [1, 2, 5, 9] — modifiée sur place

L.sort() renvoie None : écrire L = L.sort() détruit la liste. C'est une erreur très fréquente, cousine de L = L.append(x).

Tri par sélection :

def tri_selection(L):
    L = L.copy()
    for i in range(len(L)):
        indice_min = i
        for j in range(i + 1, len(L)):
            if L[j] < L[indice_min]:
                indice_min = j
        L[i], L[indice_min] = L[indice_min], L[i]
    return L

Il effectue $\frac{n(n-1)}{2}$ comparaisons, soit environ $n^2/2$ : $50$ pour $10$ éléments, mais $500000$ pour $1000$. Le tri de Python, lui, en demande de l'ordre de $n\log n$ — d'où l'écart considérable sur de grandes listes.