C18.2 : Tri par sélection

Les actions répétées sont :

• - la recherche du maximum dans la partie non triée et le placement de l'élément trouvé à la fin de la partie triée ;
• - pour la recherche du maximum, la comparaison de l'élément retenu avec tous les autres éléments de la partie non triée.

from random import randint

def tri_selection(L):
    '''
    Tri la liste L du plus grand au plus petit
    param L: (list) Liste de nombres entiers
    effets de bord : le paramètre L est modifié
    '''
    for i in range(0, len(L)-1):
        pos_max = i
        for j in range(i+1, len(L)):
            if L[j] > L[pos_max]:
                pos_max = j
        L[pos_max], L[i] = L[i], L[pos_max]

# -----Programme principal-----
liste = [randint(0,99) for _ in range(20)]
print(liste)
tri_selection(liste)
print(liste)

La preuve de la terminaison de l'algorithme est immédiate car l'algorithme est composé de deux boucles for.

L'invariant pour la boucle de recherche de la position du plus grand élément dans la partie non triée (boucle interne) est :

« L'élément à la position pos_max est plus grand que tous les éléments de i à j ».

L'invariant pour la boucle qui permet de trier un élément supplémentaire (boucle externe) est :

« La partie du tableau de 0 à i est triée ».

L'algorithme fait toujours le même nombre de comparaisons, quelque soit la liste de départ.

Si on note n la longueur de la liste à trier, dans ce cas il fait (n-1) + (n-2) + ... + 3 + 2 + 1 = n×(n-1)/2.

Remarque : 1 + 2 + 3 + ... + k = k×(k+1)/2

Le coût de l'algorithme est proportionnel à n², on dit que le coût est quadratique.