Le tri par sélection

Le tri par sélection est l'algorithme le plus intuitif : à chaque étape, tu cherches le plus petit élément qui reste à trier, puis tu l'échanges avec le premier élément non trié. C'est exactement ce que tu ferais en triant des cartes à la main : tu repères la plus petite carte du paquet restant, tu la sors, tu la poses à sa place.

Le principe en détail : pour chaque position i (de 0 à n-2), tu parcours le reste du tableau (de i à n-1) pour trouver l'indice du minimum, puis tu échanges (permutes) cet élément avec celui en position i. Après le passage numéro i, les i+1 premiers éléments sont définitivement à leur place finale.

Regarde le tableau se transformer étape par étape sur l'exemple [5, 2, 4, 1, 3] :

depart  : [5, 2, 4, 1, 3]
etape 0 : [1, 2, 4, 5, 3]   (minimum trouve a l'indice 3, echange avec indice 0)
etape 1 : [1, 2, 4, 5, 3]   (minimum du reste deja en position 1, aucun echange utile)
etape 2 : [1, 2, 3, 5, 4]   (minimum trouve a l'indice 4, echange avec indice 2)
etape 3 : [1, 2, 3, 4, 5]   (minimum trouve a l'indice 4, echange avec indice 3)

partie triee (a gauche) | partie a trier (a droite)

Le coût : pour chaque position i, tu parcours environ n-i éléments pour trouver le minimum. Au total, cela fait n + (n-1) + ... + 1, soit environ n²/2 comparaisons. Le tri par sélection est donc en O(n²), quel que soit l'état initial du tableau (même déjà trié, il refait toutes les comparaisons). Son avantage : très peu d'échanges (au plus n-1), ce qui est utile si échanger coûte cher.

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

Piège classique : oublier de mettre à jour indice_min (comparer avec a[i] au lieu de a[indice_min]), ce qui casse la recherche du minimum.